Time complexity analysis: asymptotic notations - big oh, theta ,omega

See complete series on time complexity here
In this lesson we will introduce you to the concept of asymptotic notations in time complexity analysis of an algorithm.

[richardjones]

A big applause to our beloved teachers Harsha and Animesh . Even though Harsha is not with us, his teachings will always be legendary and incomparable . Rest in peace Mr. Harsha Suryanarayana.

[mycodeschool]

Hi JoseWanKenobi. Thanks for the comments !!
When you say above, "For Big O notation, we have c.g(n), that after some point n0 will always be greater or equal than f(n)" , its the same as saying that c.g(n) is an upper bound of function f(n). C.g(n) kind of tells us that f(n) is not gonna pass me over in value ever during its lifetime now that it has crossed n0. So, O(n^2) giving us upper bound means that there is some c such that cn^2 is the upper bound. That's how we say it. :)

[AnumitKaur]

understand this:
Given condition is f(n)<=C g(n) (which is a must). This means C = f(n) / g(n) (converting it into an equality. Conversion because, as far as I know, that's how you go about solving it).

Next, be clear that n_0 is the minimum value of n from when above condition would start to satisfy. C and n_0 both being positive integers, we start with n_0 = 0.

This means putting n = 0 in f(n) and g(n). So, f(n) = 1, g(n) = 0.
Now find C = f(n) / g(n). C = 1/0. Which is impractical and also less than 1 (C must always be greater than 1). Hence, we move on to next possible integral value of n.

So now put n = 1 in f(n) and g(n). So, f(n) = 8, g(n) = 1.
Now find C = f(n) / g(n), meaning C = 8/1 =8. Which is integral. Hence, C = 8 and so n_0 = 1.

Also n_0 is called "n not" by many instead of "n zero". Both are fine.

Hope this helps.

[abuenavi]

This is probably the best explanation of this I have seen anywhere (and from books too). Thank you very much!

[emmafoley]

Since I was referring to this as a refresher, rather than in introduction, I really appreciated how brief you kept the explanation. Thanks!

[mycodeschool]

For Big-oh lets say, we have a function f(n), by finding c and n0, we are trying to find another function in terms of g(n) , like c*g(n) which will always be greater than or equal to f(n). In our example f(n) = 5n^2+2n+1, we choose g(n) = n^2 because, we can create an inequality like (5n^2+2n^2+ n^2) = 8n^2 >= (5n^2 + 2n+1) for n>=1. In most cases, we get rid of the lower order terms by upgrading them to higher order and we get such an inequality. Let me know if its still not clear.

[mycodeschool]

Yes, it all comes down to discovering the constants c and n0. Actually, If you are able to deduce the polynomial, then its not that difficult afterwards. It is technically correct to say something like f(n) is O(5n^2+6n). Here g(n) =5n^2+6n. But we typically choose values of g(n) where constants and lower order terms are dropped. A polynomial function in most cases is big-oh of highest order term. Like f(n) = 5n^4 + 6n+1 will be O(n^4), n^4 being the highest order term.

[mycodeschool]

For multiple variables, a function like f(m, n) = 6m + 4n, we need to find C and two more constants m0 and n0, such that for m>=m0 and n >=n0, cg(n) >= f(n). We may even have one constant N such that cg(n)>=f(n) for n>N and m>N, we can pick N as max of n0 and m0. Typically, in such case we will keep both the variables and try g(n) = m+n and deduce c and N = max(m0, n0). Asymptotic notations for multiples variable functions gets a little tricky.

[umairalvi]

mannn you are totally insane the you way taught the concept of big-oh no other video taught me like you do.your concepts in every video are very very clear thank you so much for all your videos of programming and related videos

[mycodeschool]

For an expression, c and n0 will not be unique, we can have many such combinations. As long as we can find any one so that the inequality is true, we are good. The inequality is different for big-oh and big-omega, so c and n0 have to be different. You can have a look at the constants in the polynomial and try to figure out a C. So, we promoted all lower order terms to n^2 so constants got added and it became 8n^2. Any C greater than 8 would fit the inequality 5n^2 + 2n +1 >= Cn^2 for n>=1

[jyotishmanghatak]

Ur teaching skills are amazing. Even after watching several videos on time complexity, I couldn't understand it properly but today u made my doubt clear. Thanks a lot

[DeepSukhwani]

The explanations are good, but for a first timer trying to understand asymptotic notations, explaining using text book way of writing sets and all, actually confuses more. I would recommend watching Harvard's CS50's Asymptotic Notations for a rather more pragmatic explanation to this and then come back to this video. It would start making a lot more sense.

[divxxxxxx]

I still remember humblefool sometimes and then come here to watch these videos. Also Animesh you're a really really great teacher. My code school is benefitting a lot of students out there. Thank you so much.

[mycodeschool]

is 'a' in your function a constant or variable? if a is a constant, then you can try to deduce c and n0 for g(n) = log2n. If we were having something like f(n) = n + log n, for positive n, log n will always be insignificant compared to n for higher values of n. So you have a choice, either choose g(n) = n + log n or choose g(n) = n, because you know that log n is a lower order term. If a is a variable, we have case of multiple variables, so we kind of have a function f(n, a) and not f(n).

[hiralsingh]

your explainations are so detailed, well versed and interesting ; just like things seemed in coaching days!!! urs is the first video where in i was able to stay focused and also enjoy! Your lectures are much better than that of CN and CB( these are really good but not as interesting as yours)
pleeeeaaasssee cover all the topics of dsa
THE STUDENTS NEED YOU!

[mycodeschool]

[2] - So, if you are unable to find out simple g(n), its still ok to find out a complex g(n). and say that f(n) is O(g(n). But because the whole idea is to simplify the time expression, g(n) should be simple and it eventually can be simple in most cases. Hope this helps. Feel free to write again.

[khaben]

I'm in love with this channel 😍😍💖💚👏👏👏

[Mercio]

Thanks! You're an awesome teacher! Greetings from Brazil.

[pawan-tdff]

Thank you so much, you have a wonderful way of explaining things. Please keep teaching

[OnyxtheFortuitous]

This is my 2nd quarter using your videos. Thank you so much.