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.
Taking notes in the comments to feed the RU-vid 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.
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.
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)
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?
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
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
ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-zUUkiEllHG0.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 ?
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 :/
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.🙏🏾
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 } }
