1

Let x be the size of an empty array. If the array grows full, a new one will be created with a length k > x. The contents of the old array will be copied to the new one, and the new element will be stored as well.

  • An array with length k is created in k steps
  • Copying an element takes constant time.

Question: How do you choose k so that each insert operation has amortized constant time, and the insertion of n elements takes Θ(n)? Prove your assumption that your choice results in constant amortized time per insert operation with amortized analysis.

My gut feeling says k = 2*n would be a good idea but I have no idea how to prove it. I don't think I understood amortized analysis at all. Any suggestions?

deranor
  • 123
  • 5

1 Answers1

0

Growing exponentially is better than constant growth. But whether to grow it by factor 2 or by factor 2.1 there is no hard rule. Please check url below for further details.

What is the ideal growth rate for a dynamically allocated array?

Community
  • 1
  • 1
Amit Dhar
  • 31
  • 2