Best case, Average case, Worst case.
Having discussed about Running Time Analysis let’s dive into its cases and some numerical.
Worst case:- Defines the input for which the algorithm takes more time or input for which algorithm runs the slowest.
Best case:- Defines the input for which the algorithm takes less time or input for which algorithm runs the fastest.
Average case:- Here we run the algorithm for any number of iterations then compute running time for each trial sum it and divide by the number of trials
= (total running time)/(number of trials)
Assumes input is random.
Note:- lower bound <= average time <= upper bound
Asymptotic notation?
As I said upper and lower bound in the previous equation we need some hypothetical boundary to classify the algorithms within that boundary. Since it is hypothetical we go for asymptotes. Asymptote is a simple straight line in many cases to which curve touches at infinity this is done to decide the boundaries for algorithms that’s it.
Big -O Notation
Big -O gives us an upper bound. Generally, we have an upper and lower bound for any given algorithm.
Represented as f(n) = O(g(n)) where g(n) is upper bound and f(n) is a function.
O(g(n)) ={f(n): there exist constants c and n0 such that 0<=f(n)<=c*g(n) for all n>=n0}
Let f(n) = n³+n²+4
Then tight upper bound for f(n) is n³ this is the maximum rate of growth for f(n) at larger values of n.
Always consider the highest degree term do not bother about coefficients.
Let’s consider some examples
1. Find upper bound for f(n)=n⁴+100n²+50
soln:- n⁴+100n²+50 <= 2n⁴ for all values of n>=11
hence n⁴+100n²+50=O(n⁴) with c=2 and n0=11
Explanation :-
Here they have given f(n) we need to find g(n) such that for larger values of n f(n) < g(n) always, the task is to find a function that is greater than f(n) for some values of n
and in the above example, we see that for n=10, 2n⁴ is less than f(n) at n=10 we have
g(n) = 20000
f(n) = 20050
So it holds good after a certain value of n that value is known as threshold value which indicates condition holds good only for values greater than n0.
Here one may also take 3n⁴ at that time values may be different try with different g(n) observe how c and n0 changes.
2. Find upper bound 2n³ — 2n²
soln:- 2n³ — 2n² <= 2n³ for all values of n >= 1
hence f(n)=O(n³) with c=2 and n0=1.
3. Try to find for f(n)=333 what would you get? put your answers in the comment.
Omega Notation Ω
Omega notation gives us a tight lower bound for a given algorithm. It is represented as f(n)=Ω(g(n)) that is for larger values of n tight lower bound for f(n) is g(n).
Ω(g(n)) = {f(n):there exist constants such that 0 <= c*g(n) <= f(n) for all n>=n0}
Let’s look at some examples
1. Find lower bound for f(n)=5n²
soln :- 5n² <= 2n² for all n>=1
hence f(n) = Ω(g(n)) = Ω(n²).
Theta Notation Θ
Theta notation gives us information about the equality of upper and lower bounds it tells whether the upper bound is the same as a lower bound.
If the upper and lower bound have the same order of growth then Θ notation will the same rate of growth.
For example if f(n)=100n+250 then f(n)=O(n) and f(n)=Ω(n) then f(n)=Θ(n) but Θ might not be same always this we will be seeing in sorting concepts.
It is defined as
Θ(g(n)) = {f(n) : there exist c1,c2 and n0 such that c1(g(n))<=f(n)<=c2(g(n)) for n>=n0}.
We can also find time complexity for algorithms or code snippets and let’s do that in a separate section.
Image sources from Algorithm Made Easy by Narshima Karumanchi.
Happy Learning! ☻📒
