Introduction to Big-O

A short introduction to Big-O notation.

Data Structures Source Code:

[story]

I think there is a typo around 11:25. It should be 3n*(40 + n^3/2) = 3n * 40 + 3n^4/2. Isn't it?

[joe]

Nice comments, everyone seems to understand this. It's always refreshing to find I'm still the dumbest guy on youtube.

[Vennard]

This is the first video I've found that actually shows how to find the function of a method. Every other video just goes straight to the math and graphs (which I do understand) however without explaining relation to the code, so this is a life-saver considering I have an exam in 1.5 hours and couldn't figure this out for the life of me. Thank you so much!

[ajayboseac]

Big-O doesn't necessarily only indicate the worst case. It indicates the upper bound of the function. Big-O, omega and theta can be used interchangeably to indicate worst, best or average time complexity.

[dustinspencer]

Great video! I am going through your playlist as a refresher before I start my masters program. Thank you for creating them.

With respect to Big-O notation, however, I believe that you have made a small mistake with semantics. Big-O does not necessarily represent worst-case. Worst, average, and best case generally refer to the state of the input data (i.e., best case for a sorting algorithm would be the scenario where the data is already sorted). Big-O, on the other hand, represents an upper bound on how much time the algorithm will take to process an arbitrarily large input.

At least, that is how I understand it.

[williammyers]

Thanks Bill. This is the proper level of introduction for one of my CS classes.

[AntonMiasnikov]

Thank you, human. It is the best short explanation I found on the net.

[anokaggrey]

Best Big O video I have come across so far.

[alexcons]

Thanks for the video, great tutorial as always!

[deepak]

too good... finally understood with practical examples

[codewarrior]

Refreshing and easy to follow tutorial, thank you!!

[shubhamjain]

8:28 it should be multiplied by n because we are not considering the time for outer loop...
Nsquare is only for inner loop...
Please explain me

[architect]

WELL; you're an exellent teacher.

[sabergun]

I like that my maths is bad and I can still follow this, credit to the author for that - thanks.

[IamMQaisar]

Shouldn't there be "3n * 40" instead of (3n/40)?
Also,
Inner loop runs 41 times instead of 40
So,


Eventually making it, 3n*41 which is 123n.

Am I right? 11:30

Eventually answer remains o(n^4)

[Cat_Sterling]

Is there a typo in the Binary Search pseudocode? At 8:36 in the end of the while loop, the variables "lo" and "hi" should be called "low" and "high", correct?

[umairalvi]

I was expecting that you will explain why the complexity of binary search is logn.

[_Anna_Nass_]

Taking notes in the comments to feed the YouTube algorithm:

Complexity= How much time and space does your algorithm need to finish. Big O Notation only cares about the worst case. It gives an upper bound of the complexity as the input size becomes arbitrarily large.

[tilakmadichettitheappdeveloper]

By dominant, you mean the term in the polynomial with the highest degree, dont you ?

[JG-qsmx]

6:27 can you please explain how it is linear time in right while loop? i is incremented by 3, so the loop won't run n times. so how it will still give O(n).