I used to think that when people didn't use 'the' it was because English wasn't their first language but I know for a fact that the person who said this one is. Is there a rule for that? People sometimes drop the 'a' too for some reason
They can be used mostly interchangeably. The phrasing notify police treats police as a concept or entity, meaning the organization which calls themselves 'police' were not notified.
Alternatively, notify the police treats police more as a group of individuals in my mind.
The more thought I'm giving this, however, the more narrow that distinction seems. I might choose between the two to make the sentence flow better, or to imply some regional/class language differences. However, the difference in actual meaning seems too small to worry about.
It is correct to use "police" with no article as it is done in the news all the time. In fact, it seems to greatly outnumber the times "police" is used with an article (at least in the news).
To test this, I searched the NOW (News On the Web) corpus for the 100 most recent occurrences of the word "police". (Some of these occurrences weren't relevant to the matter at hand because they were adjectives.) All the results were from American newspapers.
Search for yourself here. These are some of the results that I got, ranging from local to national newspapers: