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?
@WilliamFiset-videos6 жыл бұрын
Oops! I can't multiply it seems ;P The overall answer is still O(n^4) though.
@0215story6 жыл бұрын
you mean it's not a typo? :)
@WilliamFiset-videos6 жыл бұрын
byeonghan baek Sorry that's what I'm trying to imply, you're correct.
@0215story6 жыл бұрын
Thanks! Your vedio are very useful and clear explaining ! 😄
@siddhartharoy52634 жыл бұрын
@@Ruturaj22 😂😂😂😂
@joe448506 жыл бұрын
Nice comments, everyone seems to understand this. It's always refreshing to find I'm still the dumbest guy on youtube.
@Linusovic6 жыл бұрын
hahahhaha
@alottafugina91164 жыл бұрын
Are you homeless now? Did you give it all up?
@joe448504 жыл бұрын
@@alottafugina9116 No, I fooled a company into hiring me and now I write a lot of quadratic methods.
@alottafugina91164 жыл бұрын
@@joe44850 then I guess now I am the dumbest on KZbin.
@PickleRickkk-cy9xb7 ай бұрын
@@alottafugina9116 Hey, are you homeless now? Did you give it all up?
@Vennard984 жыл бұрын
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!
@yuvrajanand1991 Жыл бұрын
Bro, and u r writing comments here😂
@ajayboseac013 жыл бұрын
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.
@kaustubh_ramteke_072 жыл бұрын
so what's the point of theta, omega
@supriyamanna7152 жыл бұрын
coming here after Abdul bari;s videos!!
@supriyamanna7152 жыл бұрын
@@kaustubh_ramteke_07 In some cases, you can't get the exact average case (that is big theta), there you have to use the other two to get an idea. here omega is the upper lower bound and the big O is the upper bound, when both are same (or at least converging to the same point/functions) we can say that the average case (theta) is the same. Big O is upper bound of a function, and if I run an algo which is giving me the upper bound for a particular case(let's say worst case): I can at least derive big O and big Omega So as a verdict, on a function, we can get any case depending on the algo used.
@rohangowda2001 Жыл бұрын
true!
@dustinspencer85932 жыл бұрын
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.
@williammyers37065 жыл бұрын
Thanks Bill. This is the proper level of introduction for one of my CS classes.
@AntonMiasnikov4 жыл бұрын
Thank you, human. It is the best short explanation I found on the net.
@anokaggrey31092 жыл бұрын
Best Big O video I have come across so far.
@alexcons7 жыл бұрын
Thanks for the video, great tutorial as always!
@shmasshah4 ай бұрын
did you get anything out of this? job anything or left it after 4 videos?
@donnguyen51646 жыл бұрын
Great examples and explanations!
@shubhamjain31514 жыл бұрын
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
@jesso66703 жыл бұрын
N multiple by n square which is largest among two is n square
@deepak17256 жыл бұрын
too good... finally understood with practical examples
@sabergun5 жыл бұрын
I like that my maths is bad and I can still follow this, credit to the author for that - thanks.
@codewarrior70727 жыл бұрын
Refreshing and easy to follow tutorial, thank you!!
@Tholkappiar2 жыл бұрын
You deserve a reward👍🏻👍🏻👍🏻
@architect86755 жыл бұрын
WELL; you're an exellent teacher.
@Cat_Sterling2 жыл бұрын
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?
@IamMQaisar6 ай бұрын
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)
@umairalvi73824 жыл бұрын
I was expecting that you will explain why the complexity of binary search is logn.
@_Anna_Nass_11 ай бұрын
Taking notes in the comments to feed the KZbin 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.
@marialynanding6535 Жыл бұрын
Can I ask? What does it called on constant time to factorial time I just wanted to know because it is necessary for my presentation I want to share to them what does it called .. Thank you.🙏🏾
@tilakmadichettitheappdeveloper7 жыл бұрын
By dominant, you mean the term in the polynomial with the highest degree , dont you ?
@WilliamFiset-videos7 жыл бұрын
Yes, that's correct! But it could also mean another stronger term such as 2^n or n!
@goodvibes15812 жыл бұрын
Best as always
@akashsinghal1073 Жыл бұрын
kzbin.info/www/bejne/sIa4nJx7odF7fZI at 8:23 time i understand for inner loop time complexity should be "n(n+1)/2" but shouldnt we multiply external loop "n" complexity to make it n3 ?
@JG-qs8mx6 жыл бұрын
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).
@WilliamFiset-videos6 жыл бұрын
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
@maddcobra15 жыл бұрын
Thank you WilliamFiset for explaining.
@dejiomofaiye56604 жыл бұрын
In big O example where there are two for loops where the inner loop starting value j is sets to i. I want to believe the j value will now be 1. And also the question of what is (n) + (n -1) |+ (n-2) etc how did (n-1) become(n+1) and why are you dividing by 2
@zahideduardoz5099 Жыл бұрын
Same question haha
@esa22366 жыл бұрын
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.
@MrHatoi6 жыл бұрын
Small typo around 3:30, it says quadric instead of quadratic.
@WilliamFiset-videos6 жыл бұрын
Noted and fixed in my slides, thank you!
@Aman-nw1jp6 жыл бұрын
lol
@aritram19037 жыл бұрын
Nice tutorial...thanks
@saurabhrudrawar58876 жыл бұрын
can u post another video on this with a some tough examples? i am getting it finally so would like to know it better :)
@nickwalton11094 жыл бұрын
8:21. How does O((n^2)/2 + n/2) get us to O(n^2)?
@cablu14 жыл бұрын
Around 11:25 where it's 3n*(40+n^3/2) breaking down the problem it makes sense: 3n since it's in the outer loop but in the inside loop why is n^3/2, is it because it's nested 2 loops deep? Trying to figure it out but the only logical thing is that it's nested 2 levels deep :/
@ManishKumar-ct4sn8 ай бұрын
Its because j is increased by 2 every time: j=j+2.
@mohamedbadrismail45102 жыл бұрын
Could you share the slides, plz??
@JorgeAmengol2 жыл бұрын
1:05 Although largely used by computer scientists, I think those notations were invented by mathematicians.
@hadiyaajumun79004 жыл бұрын
"practical examples coming up..." can i have the link of your examples plz if there is any? thank you
@danimanabat57913 жыл бұрын
Thank you!!
@vophihung15982 жыл бұрын
good job anh
@MustafaAhmedAbduljabbar6 жыл бұрын
Great video thanks :)
@_productivity__nill_11315 жыл бұрын
So, multiplying two for loops will always equal n²?
@WilliamFiset-videos5 жыл бұрын
No, a single loop doesn't always have a time complexity of O(n), so the product of two loops doesn't always have a complexity of O(n^2) For example the following has a complexity of O(sqrt(n) * n) for (i = 0; i < n; i = i*i) { for (j = 0; j < n; j++) { // some O(1) operation } }
@angel-ig5 жыл бұрын
@@WilliamFiset-videos Nop, that's an infinite loop, 'i' will be always 0
@eggiweggsi6 жыл бұрын
Why is J going from 10 to 50 in the last example? Cheers
@WilliamFiset-videos6 жыл бұрын
Just to throw some spice into the mix. The loop will execute 41 times so it's still a O(1) operation.
@anthonyditizio41784 жыл бұрын
thanks
@praveenrawat65742 жыл бұрын
charlie?
@sodapopinski99226 жыл бұрын
I'm sure you heard this before bu you sound like Christopher Welch from Silicon Valley
@feliperesendez22215 жыл бұрын
It's more like Richmond from the IT crew
@BubTheOriginal3 жыл бұрын
Pro tip : Play at 1.5x speed.
@prowlus3 жыл бұрын
Cast in the name of god ye not guilty
@Tony-ow9bo4 жыл бұрын
For the love of god get something that lets you circle or underline the parts you're talking about. This is for the birds.
@sntshkmr604 жыл бұрын
Am I the only one who is not able to understand mathematical equation at 4:00?
@GodSnake0013 ай бұрын
I understand nothing☻
@IAmGDUB Жыл бұрын
This junk make no sense to me and it's making me mad bro