need explanation on amortization in algorithm
Posted
by
Pradeep
on Programmers
See other posts from Programmers
or by Pradeep
Published on 2012-11-18T18:08:16Z
Indexed on
2012/11/18
23:28 UTC
Read the original article
Hit count: 389
algorithm-analysis
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..
© Programmers or respective owner