I am a learning algorithm analysis and came across a analysis tool for understanding the running time of an algorithm with widely varying performance which is called as amortization.
The autor quotes
An array with upper bound of n elements, with a fixed bound N, on it size. Operation clear takes O(n) time, since we should dereference all the elements in the array in order to really empty it.
The above statement is clear and valid. Now consider the next content:
Now consider a series of n operations on an initially empty array. if we take the worst case viewpoint, the running time is O(n^2), since the worst case of a sigle clear operation in the series is O(n) and there may be as many as O(n) clear operations in the series.
From the above statement how is the time complexity O(n^2)? I did not understand the logic behind it. if ‘n’ operations are performed how is it O(n ^2)? Please explain what the autor is trying to convey..
2
In your case, n is the size of the array. And the algorithm is running at most once over the array. Each time it runs, it performs an operation (or calls another function) that itself runs at most once over the array. Thus, if you assume that the worst cost of running the clear() algorithm is O(n) and that the outer algorithm does nothing more expensive or proportional to that algorithm, you will run an O(n) clear() function n times.
This means that the overall cost of the function will be n * O(n) or O(n^2).
One important thing to note is that your operation is not a constant operation. When one says that running an operation n times costs O(n) she simply means that that operation is a constant operation or O(1) –meaning one that does not increase in cost with increase in size. The clear() function does not fit this description and hence you cannot say that running the clear() function n times is an O(n) operation.
Post script:
O(n^2) means that the run time complexity of the examined function will not exceed square growth for sufficiently large values of n.
In simpler words, for large values of n, O(n^2) means that the time to execute the examined algorithm over an input of size n will not increase by more than four times when n is doubled. The keyword here is large because for smaller values of n, constant factors (even when they exist as coefficients) may be significant. Theoretically, large values of n mean approaching infinity.
7
“Now consider a series of n operations on an initially empty array. if we take the worst case viewpoint, the running time is O(n^2), since the worst case of a single clear operation in the series is O(n) and there may be as many as O(n) clear operations in the series.”
if you perform n operations on an array with n elements (assuming that each operation is of order 1), you get n X O(n) –> O(n^2).
Example:
Say n=3, you want to perform 3 clears on the array.
first clear process takes 3 operations
second clear process takes 3 operations.
third clear process takes 3 operations.
total = 3×3=9=O(3^2).
The tricky part I can’t justify though is the one in italics!
4