21
Aug

# 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

• intbild says:

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

• NightLurk says:

You forgot logarithmic time complexity which is the most interesting 😀

• Kabral Mogos says:

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

• Nik0lay11 says:

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!

• Harvey Specter says:

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)

• 633K_4R1ND4M says:

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)?

• Sonal Tambi says:

Hey Dojo,
Where do you originate from?
'cause very very few people are like you… 🙂

• Piept says:

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

• kasi viswanath says:

please make video on O(logn) and O(nlogn)
Thank u so much for your nice explanation

• Boby Gandhi says:

34:08 hehe

• Kapil Garg says:

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

• Koushik Khan says:

Really good explanation 😍

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

• Anwarasrabali Hussain says:

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

• Tech Professor says:

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

• Fall in Love with Computer Science says:

Playlist for algorithm

• Cristian Dante says:

YOU SAVED MY LIFE

• Yuanjia Zheng says:

Thanks!

• Yawar Ali says:

make the video how we find big O mathematically

• SpectatorAlius says:

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?

• gfrias06 says:

Awesome explanation, thank you very much!

• Eric says:

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

• Cosmonaut Billy says:

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.

• the suresh Atta says:

To my surprise, you ignored logarithmic time ?

• Mohamed H. Kamal says:

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

• Vamos Sanjith says:

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++)
{
}

• android user says:

Excellent sir from India

• Dillon Smithson says:

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

NAH… uses Python

• VINCENT WANAM says:

stupid function

• Tushar Gupta says:

Hey can you make a in depth video on Data structures ???
Pls your explanation is the best n easiest explanation on the YouTube

• Mako Next says:

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

• ゴリラ says:

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

• Baksa Gimm says:

Now i think i can build a time machine.

• Dipanjan Chowdhury says:

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

• joseph bickerton says:

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

• ChelseafcTube says:

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.

• Mark Henrich says:

I love python, it's practically just pseudocode lol

• willzurmacht says:

Why are you so cute!?

• Ahsan Imam says:

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

• Miriam B. says:

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.

• Louis Leemans says:

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

• Ujjwal Nath says:

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

• Saeedeh Moghimi says:

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

• JD Penuliar says:

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

• Ferin Patel says:

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

• Ufuk Kayserilioglu says:

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.

• College Gamer says:

Thanks Dojo.It was very helpful as always 😃

• Jasbir Singh says:

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.

• Sumesh Sukumaran says:

Thank you

• Sanjeevi .M says:

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

• Sylus says:

Thank you ! 😍👌

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

• Sushant Kumar says:

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

• Chris Camp says:

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!

• Ankita Kiro says:

Thank you🍁🍁Love from India💜

• SUBHAM SAH says:

Please make more videos on data structures and algorithms

• Bruno 148 says:

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

• Linda Zhang says:

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

• Pawan Pandey says:

Wow. Just wow. You made it look so simple. Complexities seemed nightmare before this lecture.
Can you also please explain Merge Sort's complexity?

• Dravid Hemanth says:

you are just great!

• Carlos Heiras says:

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

• Syed Mushaheed says:

Yes I need a formal video on big oh notation

• Shubham Bhosale says:

Sir please can you make a separate video on Formal mathematical definition of Big-O ?
It would be great. Thanks 🙂

• Carlos Cab says:

I watched this shit at 2X.

• Michael Knox says:

Subscribed and liked. Thank you

• jpconverg says:

brilliant explanation!

• Sara says:

you make it look really simple ! Thanks

• Leonel Hernández says:

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?

• Pedro Santana says:

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.

• warnford says:

really nicely done with painstaking detail and examples – thank you

• R remix says:

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.

• Timofey Tsvirko says:

17:41 – how to find time complexity

• Pedro Hartmann says:

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

• Shanewaz Al Maruf says:

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

• Fr3DSky says:

thanks

• Evelyn Namugwanya says:

Excellent!!

• Yash Solanki says:

I just want some more video on this topic🙌💯
Great explaination YK👍

• I'm Rych says:

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 👌

• Eric Coelho says:

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

• Anjana Nisal says:

INCOMPLETE
Don't waste 36 mins

• Viktor Nespolo Peixoto says:

!

• Hongyi Chen says:

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

• patel savan says:

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

• Kunwar Prakhar Singh says:

This just might save my sem.

• silver says:

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 .

• M. Copeland says:

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!

• Shabbir Ahmed says:

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

• pallavi verma says:

Superbbb great

• Shivam Tyagi says:

CS Dojo,
Can you make video on binary tree and avl tree and heap?

• Sai Venkatesh says:

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???

• REAL ISLAM says:

AND WHEN YOU GO TO INDUSTRY NOBODY CARES ABOUT BIG 0(SHIT), YOU ONLY LEARN FRAMEWORKS

• Sophia L says:

Thanks a lot, YK, you are such a good lecturer, i learned more here than my graduate classes!

• AIN - Articial Intelligence Network says:

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

• Marsellus Wallace says:

Awesome ! Thank you for the video

• TheChaosLp says:

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]

let me know if theres an easier way

• Niki Izvorski says:

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.

• Gabriel Gallegos says:

Thanks!