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!
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_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.
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.
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).
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
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?
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 :/
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
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.🙏🏾
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.
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 } }
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)
czcams.com/video/zUUkiEllHG0/video.html 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 ?
Taking notes in the comments to feed the CZcams 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.
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?
Oops! I can't multiply it seems ;P The overall answer is still O(n^4) though.
you mean it's not a typo? :)
byeonghan baek Sorry that's what I'm trying to imply, you're correct.
Thanks! Your vedio are very useful and clear explaining ! 😄
@@Ruturaj22 😂😂😂😂
Nice comments, everyone seems to understand this. It's always refreshing to find I'm still the dumbest guy on youtube.
hahahhaha
Are you homeless now? Did you give it all up?
@@alottafugina9116 No, I fooled a company into hiring me and now I write a lot of quadratic methods.
@@joe44850 then I guess now I am the dumbest on CZcams.
@@alottafugina9116 Hey, are you homeless now? Did you give it all up?
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!
Bro, and u r writing comments here😂
Thank you, human. It is the best short explanation I found on the net.
Thanks Bill. This is the proper level of introduction for one of my CS classes.
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.
so what's the point of theta, omega
coming here after Abdul bari;s videos!!
@@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.
true!
Refreshing and easy to follow tutorial, thank you!!
too good... finally understood with practical examples
Thanks for the video, great tutorial as always!
did you get anything out of this? job anything or left it after 4 videos?
Great examples and explanations!
Best Big O video I have come across so far.
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.
WELL; you're an exellent teacher.
can u post another video on this with a some tough examples?
i am getting it finally so would like to know it better :)
Nice tutorial...thanks
You deserve a reward👍🏻👍🏻👍🏻
Great video thanks :)
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
N multiple by n square which is largest among two is n square
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).
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
Thank you WilliamFiset for explaining.
I like that my maths is bad and I can still follow this, credit to the author for that - thanks.
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?
I was expecting that you will explain why the complexity of binary search is logn.
Best as always
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 :/
Its because j is increased by 2 every time: j=j+2.
Small typo around 3:30, it says quadric instead of quadratic.
Noted and fixed in my slides, thank you!
lol
Thank you!!
By dominant, you mean the term in the polynomial with the highest degree , dont you ?
Yes, that's correct! But it could also mean another stronger term such as 2^n or n!
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
Same question haha
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.🙏🏾
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.
Could you share the slides, plz??
So, multiplying two for loops will always equal n²?
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
}
}
@@WilliamFiset-videos Nop, that's an infinite loop, 'i' will be always 0
Why is J going from 10 to 50 in the last example?
Cheers
Just to throw some spice into the mix. The loop will execute 41 times so it's still a O(1) operation.
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)
good job anh
8:21. How does O((n^2)/2 + n/2) get us to O(n^2)?
thanks
1:05 Although largely used by computer scientists, I think those notations were invented by mathematicians.
"practical examples coming up..."
can i have the link of your examples plz if there is any? thank you
czcams.com/video/zUUkiEllHG0/video.html 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 ?
Taking notes in the comments to feed the CZcams 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.
I'm sure you heard this before bu you sound like Christopher Welch from Silicon Valley
It's more like Richmond from the IT crew
charlie?
Pro tip :
Play at 1.5x speed.
Cast in the name of god ye not guilty
For the love of god get something that lets you circle or underline the parts you're talking about. This is for the birds.
Am I the only one who is not able to understand mathematical equation at 4:00?
I understand nothing☻
This junk make no sense to me and it's making me mad bro
same lmao