Project Euler # 19 Counting Sundays in Python
whole algorithmic change => \$O(n)\$

Your existing algorithm is quite confusing. Perhaps instead you could try a simpler structure such as:

from datetime import date

def num_sundays_on_first_of_month(year1, year2):
  num_sundays = 0
  for i in range(year1, year2+1):
      for j in range(1, 13):
          if date(i, j, 1).weekday() == 6:
              num_sundays += 1
  return num_sundays

if __name__ == '__main__':
    print(num_sundays_on_first_of_month(1901,2000))


This code is much more readable and far briefer. It makes effective use of the datetime module and its date objects.  It works by looping through every month between year1 and year2 inclusive and counting if it is a Sunday.

This runs at \$O(n)\$ time where \$n = year2 - year1\$