0
$\begingroup$

It is the time of the year again in colleges for final exams and I am preparing mine as of now and I am finding myself in hot water when it comes to understanding the running times of appending items to arrays in C.

Basically, I know there are different ways of appending items to an array, but please consider this method of appending and it's average runtime. I have managed to find its other runtimes, but not it's average.

This method to append items was introduced to me in class, and the trick is to double the size of the array when it is full, while keeping track of the next free element.

From my analysis (I hope I am right here..) we see that the price to append something is O(n) when the array is maxed out because a new array of size x2 needs to be made, and the values in the old array has to be photocopied over. However, if our array isn't maxed out then we can just append an item to the end and we get O(1) runtime.

Can someone explain to me what the average case is and what it would be in Big O notation? I am looking for a simple explanation that I can use when exam comes because it is a short answer / multiple choice exam.

$\endgroup$
  • 2
    $\begingroup$ "Average" isn't really the proper terminology here. This kind of complexity analysis is usually called "amortized". You typically look at a sequence of $n$ insertions (starting from an empty array) and look at how much time these insertions take together. Then that divided by $n$ is the amortized cost of the insertion operation. $\endgroup$ – Tom van der Zanden Nov 9 '14 at 21:25
  • 1
    $\begingroup$ You say you want the average but you descriped an amortising approch. What do you want to average over? $\endgroup$ – Raphael Nov 10 '14 at 12:11
  • $\begingroup$ The argument/proof that my algorithms book used for this, and that I found elegant, was the Accounting method. $\endgroup$ – Guildenstern Nov 10 '14 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.