Asymptotic Notations
Asymptotic Notations are like any other functional notations, which represent a simple form of a function.
You probably played a number guess game in the past. Let's play another one without the format of binary search.
Let's say the number to be found is 4. When players respond "the number is greater than 100", they are not wrong. But they are loosely close. When their guess is greater than 5, then they are tightly close. Any number guess is greater or equal to will show the upper bound.
How about numbers that are less than 4. Can't you describe a number based on lower bounds? Can we say if the number is less than 0, or -10, or less than 3? Yes, you can, and all your responses will be correct. However, the closer your guess, the "tighter the bound" will be and what we want. It is the simplest explanation I give to my students when talking about upper bounds and lower bounds.
Let's carry this numerical representation to a functional notation. Refer big O -> upper bound , big omega( Ω) => lower bound and theta Θ => average bound.
Let's say you have a function ƒ(n) = 2n + 5. And you are looking for upper bound O(g(n)), lower bound Ω(g(n)).
For big Oh, any function that evaluates greater or equal to f(n) will be correct; however, as you move away from the average bound, in this case, O(n), your result will be loosely bounded—comparing 4 to 10000000 for instance.
For big Omega on the right, it is correct to say for f(n) = 2n + 5, Ω(n) and Ω(log n). To clarify let's examine the figure below:
The average bound for f(n) = 2n + 5 is Θ(n)
The upper bound and lower bound for f(n) = 2n + 5 is also O(n) , Ω(n) respectively.
