Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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..

share|improve this question
1  
If clearing the array once is O(1*n), clearing the array n times is O(n*n) - at least according to the simplest possible analysis. –  Patrick Nov 18 '12 at 18:20
    
This is what i am not clear. If clearing the array once will take O(1) when n =1, then when there are n times its should be O(n). Hope I am clear on this. –  Pradeep Nov 19 '12 at 2:53
add comment

2 Answers

"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 = 3x3=9=O(3^2).

The tricky part I can't justify though is the one in italics!

share|improve this answer
    
hey, how is it 9. when n=3, clear operation takes 3 operations. At this point of time, the array will become empty. why will it start for n=2 again? –  Pradeep Nov 19 '12 at 3:08
    
@Pradeep, thanks for your comment. The OP mentioned "series of n operations" one of them is the clear operation. As I mentioned, the sentence "initial empty array" is ambiguous to me. It is possible that with an initially empty array, you fill it in one operation, add a value to each element, then clear it. Each of these operations requires accessing 3 elements, hence we get 3x3. At least that is what I understand. –  Emmad Kareem Nov 19 '12 at 11:14
    
Hey. I understand what you are saying but you don't write O(9). You write just 9. P.S.:- I did not down vote. –  Monster Truck Nov 19 '12 at 15:55
    
@MonsterTruck, thanks for your comment. I will edit accordingly. –  Emmad Kareem Nov 20 '12 at 1:39
add comment

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.

share|improve this answer
    
This is not clear. for example if n=5, and we ignore the outer algorithm running time, if we run the clear function first time it takes O(5). At this point the the array is empty. ow can we run the clear function again on the empty array. It should be O(5) when n =5. After the first run, the array is already cleared. –  Pradeep Nov 19 '12 at 3:23
1  
Can you post the code snippet or pseudo code so that we can see the full function? It is not clear what the author is writing about. Also, that is not how one interprets big O --O(5) does not mean cost to execute for 5 elements. Please read en.wikipedia.org/wiki/Big_O_notation for more details on what this function means as the comment box is too small. I will need –  Monster Truck Nov 19 '12 at 15:54
    
Also it matters what the clear function does. If one dumbly codes clear() to set all references to null then one will have to iterate once even when the array is all null. Once again, need to see code to give more concrete explanation. –  Monster Truck Nov 19 '12 at 15:58
    
Hi Monster Truck, I could not get a code for explanation but could get a theorem. Could you please explain me what the autor is trying to explain. Quote from the book: –  Pradeep Nov 20 '12 at 17:15
    
Theorem: A series of n operations on an initially empty array takes O(n) time: Proof: Let Mo.... Mn-1 be the series of operations performed on array S and Mio..... Mik-1 be the clear operations within the series. We have 0 <= io < .... <ik-1 <= n-1. Let us also define i-1 (i subscript -1). The running time of operation Mij (a clear operation) is O (ij (i subscript j) - ij-1 (i subscript (j-1))), because at most ij - ij-1-1 elements could have been added into the table (using the add operation) since the previous clear operation Mij-1 (M subscript i subscript j-1) –  Pradeep Nov 20 '12 at 17:25
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.