HomeОбразованиеRelated VideosMore From: WilliamFiset

Introduction to Big-O

833 ratings | 80307 views
A short introduction to Big-O notation. Data Structures Source Code: https://github.com/williamfiset/data-structures My website: http://www.williamfiset.com
Html code for embedding videos on your blog
Text Comments (36)
byeonghan baek (1 year ago)
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?
R4444 (3 months ago)
+byeonghan baek Video* - There is a typo
byeonghan baek (1 year ago)
Thanks! Your vedio are very useful and clear explaining ! 😄
WilliamFiset (1 year ago)
byeonghan baek Sorry that's what I'm trying to imply, you're correct.
byeonghan baek (1 year ago)
you mean it's not a typo? :)
WilliamFiset (1 year ago)
Oops! I can't multiply it seems ;P The overall answer is still O(n^4) though.
mikeyjk (2 months ago)
I like that my maths is bad and I can still follow this, credit to the author for that - thanks.
William Myers (4 months ago)
Thanks Bill. This is the proper level of introduction for one of my CS classes.
eaglei22 (5 months ago)
New programmers/Computer Science majors are in a good time to have topics like this simplified all over the internet. Going through this in 2008 when I first learned Big O was hard to grasp.
Wicqed Eyebot (5 days ago)
It's a great time to be alive. Most resources are available online anfv most of them are free. How lucky is this generation. Bet you never know if things will be many times better in the future.
『MasterPlayer』 (6 months ago)
WELL; you're an exellent teacher.
Skid (11 months ago)
9:04 is a famous algorithm search function. I think I get why you disregard the first half or second half because according to runtime output, the entire for loop will execute regardless whether the value was found or not. To prevent the entire loop from going all the way, and to save time, you change the boundary to mid + 1 or mid - 1 immediately to prevent the entire array from being searched and to save runtime output.
Tewodros_II (9 months ago)
I'm guessing he meant for "lo" to be "low" and "hi" to be "high".
Don Nguyen (1 year ago)
Great examples and explanations!
batabatonica (1 year ago)
t h i c c - O
sodapopinski (1 year ago)
I'm sure you heard this before bu you sound like Christopher Welch from Silicon Valley
Felipe Resendez (1 month ago)
It's more like Richmond from the IT crew
Jitesh Golatkar (1 year ago)
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).
maddcobra1 (4 months ago)
Thank you WilliamFiset for explaining.
WilliamFiset (1 year ago)
As explained earlier in the video we don't care about constant additive and multiplicative factors. Since the loop increments by +3 each time the loop will finish three times faster. This is a multiplicative speedup so it will only require one-third of the operations proportional to n for n/3 total operations. Hence, in big O: O(n/3) = O(n) because we ignore the multiplicative 1/3
MrHatoi (1 year ago)
Small typo around 3:30, it says quadric instead of quadratic.
Aman (9 months ago)
lol
WilliamFiset (1 year ago)
Noted and fixed in my slides, thank you!
Deepak sharma (1 year ago)
too good... finally understood with practical examples
Joe Bloggs (1 year ago)
Nice comments, everyone seems to understand this. It's always refreshing to find I'm still the dumbest guy on youtube.
Linusovic (1 year ago)
hahahhaha
John R (1 year ago)
Why is J going from 10 to 50 in the last example? Cheers
WilliamFiset (1 year ago)
Just to throw some spice into the mix. The loop will execute 41 times so it's still a O(1) operation.
Shade Ackermann (1 year ago)
can u post another video on this with a some tough examples? i am getting it finally so would like to know it better :)
Mustafa Ahmed (1 year ago)
Great video thanks :)
Ertuğrul Han (1 year ago)
Nice, easy, simple, understandable... Good job!
code warrior (1 year ago)
Refreshing and easy to follow tutorial, thank you!!
Tilak Maddy (1 year ago)
By dominant, you mean the term in the polynomial with the highest degree , dont you ?
WilliamFiset (1 year ago)
Yes, that's correct! But it could also mean another stronger term such as 2^n or n!
ARITRA MITRA (2 years ago)
Nice tutorial...thanks
alex cons (2 years ago)
Thanks for the video, great tutorial as always!

Would you like to comment?

Join YouTube for a free account, or sign in if you are already a member.