# Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7)

Hey everyone. In this video, I’m going to give you an introduction to Big O notation and time complexity. These concepts basically give you one way of describing how the time it takes to run your function grows as the size of the input grows. To see what I mean by that exactly, let’s take a look at a few examples here. First of all, let’s say you are given an array like this and let’s say that this array could be of any lengths. It could be one hundred elements long, a thousand elements long or even one hundred thousand elements. And let’s say you want to write a function that takes this array and returns the sum of all the numbers in this array. So, in your function you wanna add up all the numbers of this array and returns the sum. And that function might look like this function right here and I’m gonna use pseudocode here to write this function. So, first of all let’s define our function that gonna be called find sum which is going to take given array as input and then inside this function first of all we gonna initialize a variable called total to 0 and then for each i in this given array or for each number total to 0

what tool to use to calculate the time based on input and create a graph like CS dojo?

You forgot logarithmic time complexity which is the most interesting 😀

Thank you. The way you explain is very clear and understood. We are waiting more videos.

Your explanation about O(n^2) is wrong! You increasing an array size in n^2 and receive O(n^2) complexity but an algorithm itself has O(n) complexity: n^2 in and n^2 out!

For people with experience in Mathematics I recommend to put it at 1.5x speed!

(the explanation is really good, it is just that a big proportion of it is easy for people with a math background)

10:12 T=cn^2+dn+e function graph will start from 2.718(approx) for 0 input and what's the point of O(1) being equivalent to O(2) and O(0.115)?

Hey Dojo,

Where do you originate from?

'cause very very few people are like you… 🙂

Pseudopython? Add an each so it's "not" python anymore.

please make video on O(logn) and O(nlogn)

Thank u so much for your nice explanation

34:08 hehe

Subscribed to Brilliant.org using your link. Hope this would come out an as good decision.

Really good explanation 😍

What about O(n log n) and O(log n)

Awesome dude. Delighted that you explain all these factors for free also better than some paid course.🙌

Thanks Bro, I just cleared an interview with the help of this video. Love you from India

https://www.youtube.com/playlist?list=PL6_dAjIP34gJf976XKGxEsE1HnFNZcAv9

Playlist for algorithm

YOU SAVED MY LIFE

Thanks!

make the video how we find big O mathematically

Now can you explain why some people define not just O(N) but also Ω(N) & θ(N) as well? Are people misusing O(N) to mean all three?

Awesome explanation, thank you very much!

I wish u had a course ,or software engineer path, video playlist , you are really good at teaching

Some advanced stuff and I totally understand it. Neat. Thanks a lot. You explained it very well, you are good at explaining concepts. Thumbs up.

To my surprise, you ignored logarithmic time ?

Can you do a video about the formal mathematical way of big O notation ?

I started watching your videos recently! Its been grt n I have never been through so many programming stuffs in a shorter period any time in my entire life…keep up the grt work (y)

What is big O of this code

For(i=2;i<n*n;i++)

{

//COMMENTS

}

Excellent sir from India

"I'm gonna use pseudocode to explain this…"

…

…

…

NAH…

uses Pythonstupid function

Hey can you make a in depth video on Data structures ???

Pls your explanation is the best n easiest explanation on the YouTube

What I'm gonna say is complete cliché for this type of video, but dude you do explain much better than all my professors and tutors

大学の授業より分かりやすくて草

Now i think i can build a time machine.

Is there a way we can find time complexity of a function through code

very good lesson broke it down to a level even an idiot like me can understand with practical examples. thank so much

This is how teaching should be. Mathematical abstraction is used to obscure the ideas and confuse people all over formal universities, and that is what is causing most of the barrier in education. Ironically, almost all of the Mathematical abstractions come after problems have been solved practically like in this video, in some cases the abstractions come after years of studying and understanding the problem. Yet in schools they want to present the Maths abstractions in just minutes without any practical examples and expect students to pick it up without effort after they have basically obscured everything with some jargon. I am starting to think there is some conspiracy to hide knowledge as much as possible with cryptic languages. Good video man.

I love python, it's practically just pseudocode lol

Why are you so cute!?

Very well done. I took data structure in 2011 and it all came back. Thanks

I'm really curious why having two nested for loops is still n squared. Intuitively it seems like it would take longer than the single nested loop.

Holy f*ckkk you helped me so much!!! thank you!!!!

Amazing video. I was trying to learn Data Structures and this helped a lot. Thanks.

It would be great if you taught o(nlogn) and o(log n) too

Do you have the formal mathematical definition? BTW YOUR VIDEOS ARE AWESOME!

Which software do you use to explain the concepts. The software with black background and clicking on boxes and they appears

The last example is not quite correct. Finding the sum of the 2D array is still a linear time operation with respect to the size of your input. It is just that the size of your input is NOT N, it is N^2. For an array of size N, the number of items in the array is N^2, and since you have to deal with all the items, they define your input size. Given that the input size is N^2, we can call it M now, then the runtime complexity is T = O(M), which is linear with respect to the input size.

Thanks Dojo.It was very helpful as always 😃

We express constant time as O(1) as it is equivalent to O(n^0).

Anything raised to the power 0 is 1.

So we can only express it as O(1) which is not equivalent to O(2) or O(3) and so on as you demonstrated at 14:56.

Thank you

How do i learn English efficiently both writing and speaking..

Thank you ! 😍👌

Yes sir,I'd love to know a more mathematical way to recognize big O

O(Log n) and O(nlog n) notation were the one which should have required more attention

I'm sorry but the 151 people who disliked this video need Big O explained to them in crayon. This video is perfect.Thanks a million!

Thank you🍁🍁Love from India💜

Please make more videos on data structures and algorithms

What I am failing to understand is how you got the values for the array for the output of 5 and 10. My reading skills of code isn't too great and I am rusty at the moment. Can you explain it ? thanks

I wish you were my university lecturer – so happy to have found this!! 🙂 It made things make so much more sense!

Wow. Just wow. You made it look so simple. Complexities seemed nightmare before this lecture.

Can you also please explain Merge Sort's complexity?

Thanks in advance. 😃😃😃

you are just great!

estás cabrón compita, arigato chino-kun

Yes I need a formal video on big oh notation

Sir please can you make a separate video on Formal mathematical definition of Big-O ?

It would be great. Thanks 🙂

I watched this shit at 2X.

Subscribed and liked. Thank you

brilliant explanation!

you make it look really simple ! Thanks

Hi, have you seen the Berlekamp–Massey algorithm? The time complexity is defined as O(n^2), where n is the input data. Can I asume the same space complexity?

Thank you so much for explaining this. I have a quiz on Big O analysis tomorrow and I was completely lost before watching this video.

really nicely done with painstaking detail and examples – thank you

Thanks man u made my day! I was stuck at this topic at my college and u made it easy for understanding. Please make more videos on data structures.

17:41 – how to find time complexity

This is by far the best explanation about such topic. Really thanks!

I really request you for the BigO video. Please do…

thanks

Excellent!!

I just want some more video on this topic🙌💯

Great explaination YK👍

It's a shame for me that I have worked with various types of projects but I don't know basic things like this, thank you, you just made my day! 🙂

perfection for a beginner 👌

The mathematical rigorous explanation of Big O Notation would be much appreciated, brother. Thank your for the videos. 😀

INCOMPLETE

Don't waste 36 mins

!

I was about to Google Big O Notation when this video appeared in my recommendation and it clears out everything!! Many Thanks!

This is an amazing series man. You really explain soo good. Want to learn everything from you. Lots of love from India 😍😍

This just might save my sem.

Thanks a lot this was great. Would be perfect if there was a 6min version of this, kinda wordy and you lost me many times .

YK, just wanted to say how much I appreciate you for dedicating your valuable time and knowledge to the youtube community of developers. I am starting out fresh as a software developer and CS major this fall. Your videos are excellent learning tools are are helping me to grasp the discipline so thanks man!

T = c1 * n^2 + c2 * n^2 what will be the Time complexity?

Superbbb great

CS Dojo,

Can you make video on binary tree and avl tree and heap?

If all elements enqueued and all elements dequeued in circular queue then front=0 and rear = size-1 which is the condition of full queue but it is empty .why???

AND WHEN YOU GO TO INDUSTRY NOBODY CARES ABOUT BIG 0(SHIT), YOU ONLY LEARN FRAMEWORKSThanks a lot, YK, you are such a good lecturer, i learned more here than my graduate classes!

My favorite algorithm website with code samples is http://algorithmexamples.com/

Awesome ! Thank you for the video

Is this an okay way to implement the find_sum_2d function in python?

def find_sum(arr):

total=0

for i in range(len(arr)):

for j in range(len(arr[i])):

total+=arr[i][j]

return total

let me know if theres an easier way

You are soooo good i can see why Google hired you. Thanks for the explanation. It is been a while since i needed to remember all of this and it just pops in my mind when you explain it like that.

Thanks!

Awesome explanation! Love this