Big O Notation - Full Course
video description
Date: 2022-03-14
Related videos
Comments and reviews: 6
Jan
The constants insignificance towards n=infinity isn't the real reason they get cancelled out even though it's a neat explanation because our brain always forgets what we were actually searching for. We are not searching for the actual speed of the algorithm but just how it scales. Constant time expressions are the only ones that can instantly be cancelled out without even considering them as they don't depend on n and will therefore never contribute to the scaling, only the actual speed. I think the addition operator is the most confusing part for beginners because it's not arithmetic addition and more defined like the max function and n+n=n (n being a Landau expression) doesn't feel quite right. When it comes to actual programming people also often forget about the complexity of library functions they are calling and assume each function call to be O(1).
reply
The constants insignificance towards n=infinity isn't the real reason they get cancelled out even though it's a neat explanation because our brain always forgets what we were actually searching for. We are not searching for the actual speed of the algorithm but just how it scales. Constant time expressions are the only ones that can instantly be cancelled out without even considering them as they don't depend on n and will therefore never contribute to the scaling, only the actual speed. I think the addition operator is the most confusing part for beginners because it's not arithmetic addition and more defined like the max function and n+n=n (n being a Landau expression) doesn't feel quite right. When it comes to actual programming people also often forget about the complexity of library functions they are calling and assume each function call to be O(1).
reply
Luka
1:27:14 All this -MergeSort- algorithm analysis is not taking in consideration the time complexity of the in-built functions (for example, Array.prototype.slice() is being used to slice the array in two based on the middle index, and this happens log n times)
As far as I've researched (and yes it's kinda obvious), the time complexity of those methods are not constant (well, kinda depending on the used parameters; I would say, as the slice() is used in the merge function to get the none merged values, the in-built method may be done to avoid a loop if detecting the index passed as parameter is the same as the last array's index in the case there is just one element rest to merge). Still & anyways, should I consider those functions when calculating algorithm's complexity?
cheers from Argentina -
reply
1:27:14 All this -MergeSort- algorithm analysis is not taking in consideration the time complexity of the in-built functions (for example, Array.prototype.slice() is being used to slice the array in two based on the middle index, and this happens log n times)
As far as I've researched (and yes it's kinda obvious), the time complexity of those methods are not constant (well, kinda depending on the used parameters; I would say, as the slice() is used in the merge function to get the none merged values, the in-built method may be done to avoid a loop if detecting the index passed as parameter is the same as the last array's index in the case there is just one element rest to merge). Still & anyways, should I consider those functions when calculating algorithm's complexity?
cheers from Argentina -
reply
Brancu
EDIT: n-2 means n squared.
Here is a better explanation for O(n-2) for anyone who didn't understand the one in the video. For loop is a O(n) operation. A for loop inside a for loop is also a O(n) operation. The inner loop iterates as many times as the other loop iterates, so n-n, which is O(n-n). And n-n = n-2.
EDIT 2: n-3 is just n-n-n
reply
EDIT: n-2 means n squared.
Here is a better explanation for O(n-2) for anyone who didn't understand the one in the video. For loop is a O(n) operation. A for loop inside a for loop is also a O(n) operation. The inner loop iterates as many times as the other loop iterates, so n-n, which is O(n-n). And n-n = n-2.
EDIT 2: n-3 is just n-n-n
reply
Mandi
Thank you so much for this video! I finally have a good base understanding of how to calculate Big O- Your explanations were wonderful. I have a question - what tool do you use to write with on the screen and also have the code snippet on the screen?
reply
Thank you so much for this video! I finally have a good base understanding of how to calculate Big O- Your explanations were wonderful. I have a question - what tool do you use to write with on the screen and also have the code snippet on the screen?
reply
The
I've looked at so many videos trying to find a person who explained it easiest and quickly and somehow the nearly 2 hour long video is the only one that did both of those
reply
I've looked at so many videos trying to find a person who explained it easiest and quickly and somehow the nearly 2 hour long video is the only one that did both of those
reply
Den
1:06:57 It's confusing. We can do simpler:
const rightArr = arr.slice(middleIndex);
It means to start from middleIndex till the end of the array.
reply
1:06:57 It's confusing. We can do simpler:
const rightArr = arr.slice(middleIndex);
It means to start from middleIndex till the end of the array.
reply
Add a review, comment
Other channel videos
