What is Amortized Time Complexity? - Dynamic Array
HTML-код
- Опубликовано: 8 сен 2024
- Amortized time complexity analysis for an algorithm involves taking to total cost of operations in the algorithm over an extended period of time.
Amortized cost is useful when the cost of operations in an algorithm vary as per the state of the underlying data structure or time. In these cases, the average cost over an extended period of time is usually lesser than worst case operation cost.
We take the example of a dynamic array, in which the size of the array is doubled on overflow, and elements are inserted N times. We come to the conclusion that the overall time complexity should be O(N) amortized.
Link to code:
• What is Amortized Time...
References:
www.cs.cmu.edu/...
www.cs.cornell....
anh.cs.luc.edu...
Time complexity explanation:
• What is Time Complexit...
Log explanation:
• Why does log(N) appear...
@5:29 When you double the size of the array, I think this is language specific.
If using C e.g. "int a[4];" which is constant time since it's just moving a pointer.
If using java, its O(n) because the JVM specifies arrays are initialized "Each of the elements of the new array is initialized to the default initial value for the type of the array (§2.5.1)"
This gave me a bit of confusion watching the video, so I think it's helpful to point out.
Thanks for the explanation!
That's a good point :)
Thanks bro for clearing this as I was bit confused at this point
Came here to mention this. Although it's been a long while since I've done C/C++ but I think your example of "int a[4]" isn't really applicable since that is a fixed length array. This would require dynamic memory allocation so I believe that uses new/malloc. Regardless I don't think you can concern yourself with the time complexity of those operations at this level as they are beyond your control and actual time could vary significantly.
I wonder if it is always the case that default initialization requires an individual cpu operation. Seems like a hardware memset would be doable. memcpy is also going to be optimized for the particular hardware you are using.
Where did 3 come from in this??
moreover, if you want to calculate the amortized for adding a single element, you can take the cost for adding n elements which is O(n), and divide it by n, resulting in O(1)
Your explanation was much better than US University Professors.
I am a big fan of yours aaj se!! The way you deliver!! It's so damn energizing and gets straight into the brain! Too good!! Thank you so much for this!
Thanks Divya 😁
Wow, this was VERY useful! I always believed that dynamic arrays took close to O(N^2) in practice too... But this is clearly not the case.. Thanks a ton for removing this misconception!
- Akash Bhalotia
Thanks Akash!
Best video for Amortized Time Complexity explanation!
Thanks!
ive been through 3-4 text book explanations of this and it's never settled. finally get it (!) thanks bud B-)
You sir a genius..Thank you so much for your data structures and algorithm playlist
Perfect explanation, better than my lecturer. thank you
Amortized cost is used to find cost of an operation in context of sequence of operations , rather than analyzing single worst case operation. Three approaches - a) Aggregate method b) Bankers c) Physicist method.
Correction:-
Amortized cost of each insertion in dynamic array( considering doubling every time when its full) should be O(1) and not O(n). O(n) comes when we are increasing/adding array size by constant number.
you need to be clear about insert and append, both are not the same. Insertion will take 0(N) as we have to shift elements. while appending is O(1) just adding to the last index. ofc when we don't have to resize our array
The best video I've seen on this concept! Thanks so much man and keep it up, your videos are a really valuable resource.
You've come a long way from here man!
It's like you're born for this.
Keep up the good work.
Thanks!
Thank you @Gaurav, very less discussed topic in internet, I got a doubt that after pushing elements in vector, the address of first element was changing. I tried searching on google, but didn't found any helpful solution, you cleared my doubt. Thank you
Nice explanation, but major problem with audio.
Thanks Deep! The audio has improved a lot since then. You could check out the newer videos 😋
why are you considering the creation of a new empty array of size N in time complexity calculation with value of O(N). E.g. when size is 8 and you want to enter 9th element then size of array is doubled, in this calculation you considered the time complexity for 9th insertion as 16 + 8 + 1. Why the 16? If you don't consider that, i.e. creation of an empty array as O(1) operation then also the final calculation remains same. Isn't it?
@@HimanshJainYTube if we want to enter even one element after N elements we double the size fine. but how can complexity be 2*n . creating an array of 2*size will take constant time . then copying the array will take size time. then the elements inserted let say k. so time becomes size+k ??
Excellent explanation, sir! Neat and easy to understand, except for the accent. But I have to admit, you are an excellent teacher
Thanks Haiwen!
My accent would be really hard to change, but I'll try and be as clear as possible 😁
@@gkcs Found your accent perfectly clear and easy to understand from a UK native, great explanation really easy to understand much better than any of my lecturers thank you very much :)
@@ninjaweave8779 Thank you!
@@gkcs You accent is fine man, dont worry. Great english
thank you so so much for the video.
At no point do we do 3*(2N)+1, because 3*size+1 has, as size, the size of the preexistant array. 2N is the maximum we reach. Shouldn't what you write at 8:31 stop at N?
Really good stuff, thank you for your work!
Good one !!!!! Ur teaching skill and communication skill is lit🔥😀
Thank you 😁
1+2+4+8+...+2N = 2^N -1 not (2*N - 1). But yeah I understand that if the array grows like that then time complexity will reduce. then will the space complexity become more ?
Thanks for the explanation. It helped me alot.
Gaurav, that was an informative video. Cleared all doubts I had relating to the topic.
Thanks a lot. I was trying to understand the concept of amortized analysis for the past two weeks but failed. This one single video made everything clear to me!
I'm wondering on the calculation of worst case O(n^2) complexity. Why every insertion costs c= 3*size of the array everytime you double the array? You got c based on doubling array when you hit the memory. Now for every insertion you don't git that limit. Or to rectify the cals, worst case will occur for every L+1, 2L+1, 4L+1,...,2^kL+1 element only (L=size). which on simplifying gives k= log((N-1)/L) which is very small. For other N-k elements , insertion is O(1).
Thank God for subtitles.
Useful! Thanks for making videos.
Thanks Parvez!
Nicely explained
From the first second itself I understood what is Amortization means. So, basically it is an average, so to say. Correct me if I am wrong. Beginner at all these stuff
thank you sir...very nice explanation
never understood in clg! tnkx for the explanation bruh!!
Thanks... it helped me a lot
This was pretty good!
This was nice explaination. Could you please tell some book which I can refer to for learning this concept? It would be highly appreciated if you reply. Thank you !
At 9.40 , the sum of (1+2+4+...+2N) according to the video is 2*2N - 1 , but if calculated with the formula of geometric progression , shouldnt it be Sn=a(r^n-1)/r-1, and assuming the worst case , the number we gonna reach is 2N and the ratio should be 2 , so it will be (Sum of 1+2+...+2N)=1((2^2N)-1)/2-1 , which is 2^2N -1 not 2*2N-1 . Correct me if i am wrong , the video is great btw.
here no. of terms is not 2N. It's log2N(base 2). Hence, it's correct.
LOVE YOU MY MAN!!
Thank you!
Amortized analysis means instead of looking in the worst case all the time which is actually impractical you should have deep understanding of how the algorithm working and you can bring down from order n square I mean though the analysis form the poor analysis of order n square to correct analysis of order n
how doubling the size consumes time? Rather it should be a space issue and should affect the space complexity, na?
Check out how the operating system allocates space to a program.
@@gkcs so its space complexity but not time complexity
Exactly! I have looked in some places online and reputed sites. There i found that amortized cost for insertion in dynamic array is constant time not O(n). Rather, the worst case time for insertion is O(n) which Gaurav has pointed to be O(n^2) .
@@shishirjha if we want to enter even one element after N elements we double the size fine. but how can complexity be 2*n . creating an array of 2*size will take constant time . then copying the array will take size time. then the elements inserted let say k. so time becomes size+k ??
kaha se laate ho itna confidence
excellent explanation!
Thank you so much for this explanation really clear, you have what i can see next?
Could you explain how to get 2N*2-1 from the geometric formula in 9:41?
Sum of geometric series : S = (a * r^n - 1) / (r-1)
For that question, n = logbase2(2N) + 1 and a = 1 , r = 2
S comes out to be (2N * 2 - 1)
Thanks, Sir, but I have one doubt when we reach the end of the array and create a new array of doubled size, so when we create an array of doubled size will it require 2*n time complexity?? The copying of old elements to the new array will definitely take old size(n) time complexity, but the (2*n) time complexity part of doubling the array, I couldn't understand.
I also have same doubt. Do you know the answer now? If yes, can you please put it as a reply to my comment
@@vansh2k6 No, I haven't got the answer till now, I am still unable to understand this
Yea it will require 2N cause you double the size of the the array(you create a new array of double size of the previous array) and when you copy all the past elements you need N time as well, so will be 3*sizeof N, hope it helps you brother.
Great video brother.
hai the video is great but I have a doubt atlast shouldn't we divide it by N so the answer is a constant 13. cause you said in the intro it is an average for extended period of time. Another site has explained Ed the same example with result of O(1).
We could do that too. Total complexity is O(N). That gives us an amortized complexity of O(1).
constant 13 or 3??
what they mean to say is that each operation would be of O(1) so n operations would be of O(n)
In the worst case, the number of elements that are going to be inserted should be around 2N - 1 and not 2N ?????????
Can anyone help me ?
if we want to enter even one element after N elements we double the size fine. but how can complexity be 2*n . creating an array of 2*size will take constant time . then copying the array will take size time. then the elements inserted let say k. so time becomes size+k ??
Why doubling the size of the array is taking 2 and not 1?
Hi gaurav,
How do you implement reverse dns using tries?? Please make a video on that
Great video bro but the audio quality was not that great
Sir can please make video on Dirichlet Convolution and Treaps .
khub bhalo!
Too good... It is very helpful.. but does arraylist double the size or increase it by 50%?
I think it doubles the size. Will have to revisit the documentation to be sure :-)
keep it up dude...
Thanks!
where u r cpopying elements of new elements??
Very good explanation but where is the code??
github.com/gkcs/Competitive-Programming/blob/master/src/main/java/main/java/videos/DynamicArrayMain.java
You can check the video description for the code explanation link 🙂
can somebody tell me why we are creating a new array with x2 the original array length? Why dont we triple it or simply make a new array that is only 1 size bigger? is there something special about doubling or is that just how it is?
Did you understand the analysis in the video?
@@gkcs Yea I understand why adding elements in a dynamic array can look like O(n^2) but thru amortized analysis, the problem is actually O(n). My question is when we are adding another element in a dynamic array that is filled, do we always make an empty array that is double the size of the original array? Sorry if this question is too petty
@@lukekim825 I know this is 8 months old, but anyways. The doubling is arbitrary and based on the implementation. You could increase it by 1, increase it by 50%, double it, triple it, it's up to the specific implementation. However, there is a trade-off to each of these. A lower increase each time would result in less memory being used, but needs to increase in size more often. A larger increase size is the opposite, it needs to increase less often, but uses more memory.
Good explanation. Bad audio.
your sound quality of this video is not well,its difficult to understand
How can the cost be 1 or (2*n + n)? How are we getting the value '2*n' is it the cost to create the array?
Watch the video again.
@@gkcs if we want to enter even one element after N elements we double the size fine. but how can complexity be 2*n . creating an array of 2*size will take constant time . then copying the array will take size time. then the elements inserted let say k. so time becomes size+k ??
Gurav sen . Why can't you type... You went through a wrong approach
Cool hairstyle!!
Hahaha, thanks Rahul :-p
What if I wish to resize the array by adding 2 and not by doubling the array. Meaning every time the array is full I wish to increase the size of the array by 2 and not double the array size by existing size. what will be the amortized cost of this?
Think about it and let me know. 😁
It's not going to fare well, btw.
@@gkcs Trust me i have spent like more than 2 days thinking over it, dint get any solution . It would be great if you could help me out in this :D
@@pushkarajsarnobat8884 When you assign a new array, the time required is proportional to it's size.
If for every two elements, we need to assign an array of it's size, it's a problem.
Start with size 2.
Insert.
Insert.
Now make the size 4. Insert insert.
Now make the size 6.
On every 3 inserts, you are assigning a new array. Cost for n elements will be 2+4+6+...+n. That's O(n^2).
@@gkcs I'm sorry I'm not following you on this. My question is I want to try to increase the size with every insert by just two over the previous size. What is the amortized cost per insertion in this case? Meaning How much should be the cost of inserting a new element and what should be the cost of copying the existing elements into a new array
@@pushkarajsarnobat8884 You need to watch the video a few more times.
thank you
an awesome explanation but according to me , time complexity for such an algorithm must be constant. Do tell me after considering this example in the link : www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/
Thank you
my ans is 2N - 1 not (2N * 2) - 1 plz clear my dought
-----------------------------------------------------------------------------------------
gp = a(r^n - 1) / (r - 1)
1+2+4+8+......+2N = 1(2^log(2N) - 1)/(2 - 1)
= 2N - 1
plz explain how 1+2+4+8+......+2N = (2N * 2) - 1 derived
Wht is d time complexity of insertion and deletion in an array
Infinity :)
@@gkcs ty☺
Correction::
x should be log(2N)+1 instead of log(2N
)
Isn't amortized insertion runtime is O(1)?
Yup. Total time is O(N), which makes the amortized insertion time O(1).
Can anybody tell me , how to be good in time and space complexity??
Please go through first 4 chapters of the book- "Introduction to Algorithms by CLRS" and practice the problems as well.
This analysis is wrong, insertion in dynamic array is amortized constant time. Look here - www.quora.com/In-programming-languages-where-an-array-grows-dynamically-in-size-it-is-not-a-concern-because-it-is-O-n-time-complexity
Isn't that exactly what is mentioned in the video?
For n insertions, O(n) time. That gives an *amortized* complexity of O(1) => constant time.
www.google.com/search?q=amortized+meaning&oq=amortized+meaning&aqs=chrome..69i57j0l5.2356j0j7&sourceid=chrome&ie=UTF-8
sir isnt the sum of gp (2^2N)-1
I mean if sum of gp given as (1 2 4 8 16 ....2N) is a((r^n)-1)/r-1 where a=1 and n=2N and r=2
then shouldnt it be (2^2N)-1 . By the way great work and really appreciate the enthusiasm and simplicity of your work
how n = 2N
n is log 2N base 2
So It Should be 2N -1 ,how did it come 4N-1 I didnt understand.
Sn = 2^(n-1) => n = log4N after the sum is 2N = 2^(n-1) it multiplies the right side so it is now 4N = 2^n and => n = log 4N. So 3(2^(log4N-1))-1 => based on logarithm formulas a ^ log a x = x (where a in the exponent is the base of the logarithm) so we can get the result 3(4N-1)-1 = 12N - 3 - 1 = 12N - 4 => O(12N) or O(N).
Dont get y sm1 wud dislike the video
Please make videos in hindi