We have a dynamic array with the size of Fibonacci numbers. Assume that F(k) is the array's current size(F(k) is the k-th number of Fibonacci series). We have two rules here: 1)If after inserting an element in the array, the number of array elements is F(k-1), we create a new array with the size of F(k+1) and copy the previous elements to the new array. 2)If after deleting an element from the array, the number of array elements is F(k-3), we create a new array with the size of F(k-1) and copy the previous elements to the new array.
At first, the array is empty and has size of 2. We want to show that for every sequence of actions(insert or delete), every action has amortized time complexity of O(1).
For solving this problem, I realize that there is at least F(k-1)-F(k-2) actions taken between two array growing actions, and copying the elements take O(F(k-1)) time. Also, there are at least F(k-2)+F(k-3) actions taken between two array shrinking actions, and copying the elements take O(F(k-3)) time. Can you help me solving this problem?
The amortized analysis is summing each time of copy which is T(n) = F(1) + F(2) + ... + F(k) if we suppose n = F(k). We know that T(n) = F(k+2) -1.
As T(n) = F(k+2) - 1 = F(k+1) + F(k) - 1 = 2F(k) + F(k-1) - 1= 2*n + F(k-1) - 1< 3n - 1, hence amotized cost is T(n)/n < 3 and it means T(n) = Theta(1) in amortized sence.