-1
$\begingroup$

I have two questions.

  • My book: "We must ensure that the total amortized cost of a sequence of operations provides an upper bound on the total actual cost of the sequence. This must hold for all sequences of operations."

My question is:

  • Why is this important? (I know it maybe stupid, but I really would like to understand this.)
  • And does amortized analysis only include sequences of data-structure operations?
Improve this question
$\endgroup$
1
  • $\begingroup$ cstheory.stackexchange.com/faq : This is not a "research-level question in theoretical computer science". "[Q]uestions are considered to be 'research-level' roughly when they can be discussed between two professors or between two graduate students working on Ph.D.'s, but not usually between a professor and a typical undergraduate student. It does not include questions at the level of difficulty of typical undergraduate course/textbook homework/exercise." $\endgroup$
    – jbapple
    Commented Jun 12, 2011 at 18:53

1 Answer 1

Reset to default
3
$\begingroup$

I am again restating what has been said.

The amortized analysis formally introduced by Robert Tarjan involves considering the whole sequence of operation throughout the algorithm. The analysis is based on a simple practical phenomenon that when we run any algorithm there are some operations which are cheap and some are costly but overall the costly operations do not force the algorithm to perform very badly. There is simple charging argument involved that there are enough cheap operations that account for the extra cost paid for the costly operations.

An easy example includes when you are simulating a queue using two stacks. A little involved analysis comes in disjoint set union problem using path compression which has inverse ackermann funtion complexity on an average.

It is important to note that it is not same as average case complexity analysis or the probabilistic analysis. In this we consider the worst case analysis of the algorithm as a whole (instead of each operation separately). Now since we are talking of worst case complexity, the analysis becomes important to prove the algorithm efficiency as the algorithm's performance will be upper bounded by the amortized complexity. However if we do take each operation's worst case analysis separately then our analysis might be quite loose as a whole.

Improve this answer
$\endgroup$
2
  • $\begingroup$ a lot of material is available on net, try to read in for proper understanding. $\endgroup$
    – singhsumit
    Commented Jun 12, 2011 at 17:04
  • $\begingroup$ i couldn't get that why both the answers have been down-voted. $\endgroup$
    – singhsumit
    Commented Jun 12, 2011 at 19:05