What's the difference between those two? I've tried to ask Google but got very mixed results -- some people say it's the same, some that one of them is illegal and the rest offer other explanation, for example "on" means immediately, without any time for preparation and "at" with some time for preparation.. what's the truth?
I have heard both, and probably use both myself undistinguishly. My usual sources conflict on that one, actually. The New Oxford American Dictionary, which is, well, American, says:
On the other hand, Merriam-Webster’s says
The Corpus of Contemporary American English agrees with the latter, as it gives 33 hits for “at short notice” against 187 hits for “on short notice”. Google ngrams gives the same picture, but slightly less contrasted:
To put someone 'on notice' usually means telling them that they are going to lose their job after the passage of the duration of time that is specified in their contract. Generally, I would take 'on notice 'as notification of something that is definitely to come.
'At notice' can refer to something that has already happened or to something that may or may not happen