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.