Little Notation

The difference between the little and big notations have always confused me. This post is an attempt to sort them out. I have been encountering this dilemma every time I go back to my problem set in school. I always find myself referring to my Kindle to refresh my memory.

So what are the differences?

• Little notation denotes a bound that is NOT asymptotically tight. – I used to think that was waaaay bigger compared to because come to think of it is bigger then right? Apparently not big enough. When I tried graphing it and zoomed out 100x, their lines were near each other.
• Little notation requires that the condition holds true for ALL positive constants c that is multiplied to – this is the most important distinction of them all. If one says that , then for ALL positive constants c and some , should be .

Phew, that was some definition and it wasn’t even the original one . I have always found myself hard pressed to remember and apply the definition above because I am lazy and I like a methodical quick fix (with emphasis on the word methodical).

So a technique I am using is graphing of both functions on a piece of paper. An easy starting point is to let where one can easily see from the graphs of both functions if indeed is for all . If it is, then the condition should hold true for .

One gotcha, however, is that c can also be anything between 1 and 0. Going back to my previous dilemma, is It seems at first that the answer is yes for but a closer look reveals that for which is the condition does not hold anymore. Hence, .

UPDATE: Since I have rarely encountered the use of the notation, one mnemonic I have devised today to help me quickly process a statement like ‘is is to quickly apply the form to the statement. As such, if I see a the statement like , it quickly registers as .

Advertisement