The Ultimate Big O Notation Tutorial (Time & Space Complexity For Algorithms)
Вставка
- Опубліковано 20 лип 2024
- Free DSA Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Big O notation is very important for software engineering interviews. It really shows your capacity to critically think like an engineer.
The question that Big O answers is this: “how does the speed of this algorithm SCALE as the input to the system SCALES." That is it. It is a question of scale, not precise numbers. This is why we drop constants.
More precisely it is saying that if we give this algorithm VERY LARGE input, what will the UPPER BOUND of the runtime be? What will that tail behaviour be dictated by?
We say O(N) but what is n? Never say "n" without knowing what n is. Know what n is. Is it the string length? Is it the array length? Is it the number of nodes in the tree? What is it?
When we talk Big Oh we normally calculate the worst case and state that as the time complexity, hence giving it an upper bound that it cannot cross and hugs closely.
Space is calculated just like time complexity, do not be confused, but the question shifts to: “how does the space usage of this algorithm SCALE as the input to the system SCALES."
I know you want to memorize the "shape" and "pattern" of certain code but do not do this. Understand what is happening.
You will actually need to know what is going on to know them in their worst, average, and best case (although we care most about the average and worst).
It will help you find the optimal solution if you know the best complexity you can reach, it implies a method you can use that famously has that time complexity.
If you hear log(n) you know that the solution will use binary search or some algorithm that halves the input somehow...
In an interview you can't guess and that is the whole point of this, you will be put on the spot and have to explain. Explain confidently, be precise.
If you don't understand why something has the complexity it has don't be ok with not understanding, understand it, find out why and really think about what is happening. This will make you a stronger thinker and be able to tackle harder and harder problems.
Also, recursive and backtracking complexities are harder to calculate so just practice, those come with time and experience. Don't be discouraged...
+++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech - Наука та технологія
The way the camera moves and the speaker is acting makes it feel like someone is about to bust in and erase all his whiteboards at any moment 😂
Great video!
Hahahaha that was the case. 2nd video I ever did
This is the Blair Witch Project of Big O :)
I think this is one of those videos that will really keep you up rather than making you want to go to sleep. It's not boring. And the explanations are so lit.
thanks!
You're lit.
@@BackToBackSWE Your channel is excellent. Thank you for your educational content.
Simply the best explanation on the whole internet. I really like how he points out what he has done wrong in the past so we don't do the same. Thank you. :)
thanks - he is here
Table Of Contents: (I want to redo this video, the video is overexposed in lighting)
Messing Around 0:00 - 0:17
Big O Introduction 0:17 - 0:43
O(n^2 )Bounding Example 0:43 - 1:33
Upper Bounding 1:33 - 1:51
The O(n) Mistake 1:51 - 2:38
Notating min() & max() 2:38 - 2:56
O(1) "Constant time" 3:07 - 3:46
O(log(n)) 3:46 - 5:43
O(n) "Linear time" 5:43 - 6:30
O(n * log(n)) 6:32 - 8:09
O(n^2) 8:09 - 9:09
O(2^n) "Exponential time" 9:09 - 9:40
O(n!) "n-factorial" 9:40 - 10:55
Considering Tradeoffs 11:01 - 11:34
Why To Optimize Time 11:34 - 11:58
Space Complexity 12:02 - 14:38
DO. NOT. GUESS. 14:44 - 15:40
Leveraging Our Complexities 15:40 - 16:30
Wrap Up 16:30 - 16:59
HUGE IDEA. Time complexity must be at least the space complexity. If you deduce a complexity and this does not happen then something is wrong. This is because to use space we must use time (space is tightly bound to the time that it takes to use it). Due to this relationship, space ALWAYS has at least a loose lower bound on time if not very close.
I will make a part 2 to this video to expand with nuances like this in complexity theory.
Back To Back SWE excellent explanation God bless🙏🏼
thanks
THE BEST, CLEAREST BIG-O VIDEO BREAKDOWN YOU WILL FIND ON UA-cam!!!
Thank you so much for making this, it has really helped me understand things better!
Never seen that many whiteboards before.
yeah
This is the kind of video by which people like me, who are introducing to this world, will buy access to your platform, never stop making them, excellent explanation bro, I finally understood this concept.
haha, well nice
Dude, this video introduction to Big O is what I needed! Blessing from the gods!
nice
A tripod is a portable three-legged frame or stand used as a platform for supporting the weight and maintaining the stability of some other object. In photography, a tripod is used to support, stabilize and elevate a camera, a flash unit, or other photographic equipment. Tripods are available in various sizes and materials and can be purchased from many retailers such as Amazon and Best Buy.
🤣exactly my feeling right now while suffering from a headache after watching this.
Love your energy bro! Thank you for your great explanations to so many concepts
Finally an introduction to Big O that actually makes sense!! Thank you.
sure
thank you soooo much!!! seeing you so passionately talking about this encourages me to learn more about it. great great work
haha nice
Thank you for the first 11 min presenting solid examples related to each big Oh. Fantastic work.
hey
Thank you! It helps me (a beginner) get a brief understanding of all those concepts in such an easy way.
Nerd: "you can't buy time"
RTX3090: allow me to introduce myself
lmaooo
This video is one of the most complete and engaging i have seen
Thanks for the tutorial - thumbs-up given. The most important comment you made was toward the end of the video: it is impressive to state the space-time complexity. For interviews, it always helps to create an air of authority, regardless of how practical it would be to write production code that relies on the what you are being tested, which in all likelihood you never will :)
thx
I just love these videos, the presentation style really resonates with me. Great job.
thx
Very simple to understand. The teaching method is unique and efficient :) Thanks a lot for doing this :)
sure
From the bottom of my heart, thank you so much for the gold knowledge
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Ben, you are the MAN. I wish I could attend a Bootcamp taught entirely by you. I go to Columbia and it's extremely difficult to keep up with the speed at which the curriculum is taught. Your videos really help create a baseline of understanding.
haha, I am but a man, a lot of videos left to make
oh my god same I got to Columbia now. Were you doing data structures?
Wow bro you really kill the n * log (n) part. Thank you!
sure
Great video❣️
Helped me alot
I have watched many videos on big O notation but no1 has ever explained it in this easy and simple manner
Great job sir👍❣️
great and thanks
wow! It is the ultimate Big O notation tutorial. Awesome work, please keep doing the same. Thanks a lot.
thx
Out of the ones I checked out, this actually explains WHAT the concept is before jumping into some arbitrary code. Thanks!
Glad to hear that
Subscribe to our DSA course with a flat 30% discount for some amazing content b2bswe.co/3HhvIlV
Thanks for making this interesting presentation! I love your energy!
sure and thanks!
Again, I love these videos. Thank you very much!
Sure!
Your videos have been really helpful to me and it seems like some of the things that trip me up sometimes also tripped you up as well.
"We can buy memory, but we can't buy more time." That's some deep stuff right there.
Such a great and helpful video. You explained this sos well
I love this channel. I wish I could like videos multiple times haha.
haha nice
Great video it really clarifies Big O in relation to the search types
ye
Thanks for uploading videos like this!
This is the best explanation! thank you so much!
sure
Thanks you
My all doubt about algorithmic complexity is now cleared🙂
nice
Subscribed you did a good job explaining the material thanks
yuh, welcome
To be honest, this is by far the best one!
now please make a vid where you go through actual code, I am talking about actual code, not some rubbish nested for loops just to print the name or number. That will help in practically applying these concepts.
ok
Love this guy! Keep it up!
ur name is cool
Great explanation! Thank you.
sure
Prepping for Fall hiring season. Botta watch/learn from your videos
great. welcome to the party.
Good Explanation! A camera tripod would have helped though :)
this was my second video ever jeez guys
Amazing explanation!! great job!!
thanks
very good explanation, watch your video everyday on my train to office is my habits now.
wow, that is so cool, I'm flattered
Watching this was fun. Thank you!
Thank You, Glad you liked it.
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends :)
amazing energy and well explained. huge thanks!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Cool! Great job, thank you!
sure
Is the triangular work @ 8:45 a graph of number of comparisons (y) vs index (x) ? That's how you would get a triangle imo. Also from what i know about work (from physics) work is calculates as the area under the graph. Since it is a right angle triangle, we can calculate the area as 1/2 * base * height which equals n^2/2 which then gives us the complexity of n^2.
What an amazing lad. Hope he reaches heights. thanks for the clear explanation
Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
Great video, interview bytes at last on (15:43) was really impressive..
Clear and precise. If I get an A on my final tomorrow, I'll dedicate it to you.
ok
Thanks for saving my life!
That was AWESOME ✌🏻👨💻🔥🔥🔥🔥
Holy shit. It makes sense. Didn’t expect that. Thanks lol.
nice
My god im so glad I found this channel.
hey - ben
very helpful thanks for making this video.
sure thanks for watching
Thanks. You are a great teacher
Thanks for this video!
sure!
could u make another video with a detailed explanation for the space complexity
?
Thanks, Sai
yes
Amazing content!
Very good explanation...unlike other videos I can relate to ur teaching cause u stress on the points which u urself found difficult to understand
thanks and great
amazing!!! Better than stackoverflow, and professors that taught me.
haha, I'm working on redoing this video. It is badly exposed.
Back To Back SWE hahah could you give more examples in the new vid?
@@123Azns yeah. it will be amazing.
Great one!!!!!!!!!
Great explanation, thank you
sure
The clarity!
thanks
This is the best video on big Oh.. I also like ur style bro
thanks
I am glad you didnt use a potato to record this, instead you opted for a bowl of jello. I was dizzy at times, but overall. Great content!
Sir, can we say O(log(n)) means "half of n or half of the common runtime" of the algorithm? So, if anyone asks that what is O(n*log(n)), we can say its O(n*(n*1/2)) which is O(1/2*n^2) and drop the constant which becomes O(n^2)?? Means O(n*log(n)) = O(n^2)???
very clear and on point
Happy Holidays! Really glad to help 🎉 Do you know about the BacktoBackSWE 5 Day Free Mini Course? Check it out here - backtobackswe.com/
Hi mate, 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?
No I haven't :/
No worries. I was doing this analysis and basically the time complexity can be calculated according to biggest tasks involved, where n^2 steps are taken. When calculating the space complexity is a different story because, I was mainly considered the vectors that I used, in my case 4.
the best explanation of big O thanks! camera wasn't stable enough :/
ik, 2nd video we ever made
thank you!
This man doesn't use dots for bullet points he uses transmutation circles
Thanks!
5:59 really helped things click for me, thanks!
I just felt like i watched video at 2x speed. so much useful content in so less time.
Studying the behavior and complexity of algorithm can be super confusing, especially considering mathematics is involved and not all developers are well schooled beyond basic algebra.
This is a pretty good introduction in my opinion, to get your head around the basics.
thx, old video tho
@@BackToBackSWE Hey, at least the info is still good.
Simplest explanation of Big O period.
hello
@@BackToBackSWE hello world :)
Thank you!
sure
thanks a lot brother.......n im your new subscriber!
welcome
Nice job!
thanks
dude i love you
revisiting thanks !!
nice
This video is GOATED
yes
It forms what it look like a triangle--> Didn't understand this point for O(n2), how it formed a triangle?
what year are you? great video btw!
2nd
Subscribed ❣️✨
At 8:34, how did you go from 3 comparisons of an array to form a triangle?
I dont remember
Thanks for share it
thanks
Talking about time complexity, it's great to watch your video and do some further study on it because it's almost a basic skill during interviews. At least from my previous interview experience, both facebook and bloomberg interviewers were willing to know if I could accurately state time & space complexity. Highly recommend Cracking the Code Interview Chapter VI. Big O, where you would deeply understand the practical ways of solving this issue.
The answer here clearly explained how we should calculate time complexity for the recursion calls: stackoverflow.com/questions/43298938/space-complexity-of-recursive-function
Nice, thank you for sharing.
new WhizBangArray(n) # picks the best container type for n
"They don't OOP!?"
Come on lazy iterator! 😜
I got the job!
wonderful!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Doesnt that make nlogn then 8 times 3 making it 24 as complexity????
greate explanation
In O(n) complexity, when it is 3*n the linear graph line doesn't become sterper but shifts up 3 units.
Great explanation!
What? Can you timestamp it? Multiplication by a constant factor makes a line steeper. Shifting up is addition.
@@BackToBackSWE Yeah! Sorry, I was just confused between multiplication and addition on functions. You again made it clear. Thanks alot!
thanks a lot!!!♥
sure
Awesome video! I got very dizzy watching it though :( still thanks the content is great!!
old video, thx
8:08 woah woah... no need to get personal
old video - sorry if I said something weird
@@BackToBackSWE lmao no u just said an O notation of n^2 was innefficient
i cant do better >:
Very good! I just wish the video footage wasn't shaky!
Glad it was helpful and sorry about the footage! 😄 Also check out our FREE DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
love you man...
glad it helped
Bruh I need more practice on this! What can I do?
Hey your are best content creator
no u