But when we talk about the time complexity of a recursive program, let's say finding fibonacci series, we take into account the number of times a single function calls itself recursively but here we're doing it in a different way. I am a bit confused as to if we apply the same procedure to the fibonacci algo, how would we find the time complexity.
Something that has been bugging me about merge sort is it classifies the operations of dividing as O(1). However the slice operations create new arrays every time which is technically (n / 2) yet it isn't included in the analysis. Why is this considered constant time?
Good point. It actually depends on the implementation. You can make the splitting of the array O(1) by not actually splitting the array but instead just using the same array and keeping track of where you are in the array by just using the array’s indexes. That is the more optimized way to do it. But even if you consider that we are making copies of the array at every level, and also need to touch every element to compare values, it is still O(n log n) because O(2n * log n) simplifies to O(n log n)
Why are we considering level of operations instead of number of operations... It seems that time complexity has to be O(n.2^n) right. Like if we compare this tree architecture with the previous video, O(2^n) complexity looks more relevant than O(log n). Please correct me if I am wrong.
The tree will be comprised of log base 2 of n levels. At each level we need to touch every element of n. So the time complexity is number of levels times n. So O(number of levels * n). number of levels = log n, so time complexity is O(log n * n) or O(n * log n) or O(n log n). Does that help?
![Big O Notation Series #10: Log n Complexity Explained With An Iterative Function [Logarithmic time]](http://i.ytimg.com/vi/SfygqfMVSgw/mqdefault.jpg)
![Big O Notation Series #10: Log n Complexity Explained With An Iterative Function [Logarithmic time]](/img/tr.png)
Wonderfully explained!!!Thank you for elucidating so much on time complexities. Best video I have even seen on YT regarding Time complexities.
Your comment makes me smile 🙂 Thank you 💙
Thank you. Just...thank you. I'm a frontend dev and I've always considered this stuff way over my head, but it's slowly starting to make sense.
That’s great! Things always seem more complicated than they are in the beginning. Keep it up!
Really helpful and clear thank you so much... 2 min to understand the time complexity is amazing!!!
That’s great news. I’m glad it helped you!
This helps me a lot. Thank you so much!! Love you!❤
Happy to help! ❤️
As usual you are exceptional ✨!
Thank you! 🥲
Good explanation, thank you!
Thank you! I’m glad it was helpful😆
THANK YOU
Happy to help! 😊
But when we talk about the time complexity of a recursive program, let's say finding fibonacci series, we take into account the number of times a single function calls itself recursively but here we're doing it in a different way. I am a bit confused as to if we apply the same procedure to the fibonacci algo, how would we find the time complexity.
There’s a video in this series that explains Fibonacci time & space complexity
Great video!
Btw what is the note taking app/setup you are using on your iPad to explain the conceptual part of this video?
I think it's called goodnotes but I will have to check later
Something that has been bugging me about merge sort is it classifies the operations of dividing as O(1). However the slice operations create new arrays every time which is technically (n / 2) yet it isn't included in the analysis. Why is this considered constant time?
Good point. It actually depends on the implementation. You can make the splitting of the array O(1) by not actually splitting the array but instead just using the same array and keeping track of where you are in the array by just using the array’s indexes. That is the more optimized way to do it.
But even if you consider that we are making copies of the array at every level, and also need to touch every element to compare values, it is still O(n log n) because O(2n * log n) simplifies to O(n log n)
you're great. thank you
Thank you 🙏 🙂
Why are we considering level of operations instead of number of operations... It seems that time complexity has to be O(n.2^n) right. Like if we compare this tree architecture with the previous video, O(2^n) complexity looks more relevant than O(log n). Please correct me if I am wrong.
The tree will be comprised of log base 2 of n levels. At each level we need to touch every element of n. So the time complexity is number of levels times n. So O(number of levels * n). number of levels = log n, so time complexity is O(log n * n) or O(n * log n) or O(n log n). Does that help?
Got it. Thankyou very much 👏
Thank you for this. I was wondering what programs and software you use to write and record your desktop?
You’re welcome, I’m just using the screen recorder that comes included on my MacBook
Thanks!
do you have any video on the Quicksort?
Not yet, but I’ll add it and the other sorting algorithms to my backlog 🙏
1 min wasted for opening a box
4:10... time to eat something =P
🤣