In wikipedia, I was reading about amortized analysis and I read the following definition:

" Instead, amortized analysis averages the running times of operations in a sequence over that sequence."

Could someone explain to me what this means? Logically and with an example?

  • 1
    $\begingroup$ The page already gives 2 examples. Have you read them? $\endgroup$ May 4 at 12:28
  • 2
    $\begingroup$ This is not a definition. It is an informal explanation. $\endgroup$ May 4 at 12:40
  • $\begingroup$ The sentence just says that the amortized time is the average time. $\endgroup$ May 5 at 13:26
  • $\begingroup$ @YvesDaoust if we consider the process of plugging in an element in an array. The amortized time complexity is $\Theta (1)$. At the same time, in Wikipedia it is said, that the amortized time is less then the individual time complexity of an operator. At the same time $\Theta (1)$ is the result of $\Theta (1)=\frac{\Theta (n)}{n}$, and this last eq. to me looks like we are calculating the total amount of time for n operations, divide by the total amount of them, to find the time for a single operation. $\endgroup$
    – imbAF
    May 7 at 13:38
  • $\begingroup$ @YvesDaoust But this contradicts what I just said : "the amortized time is less then the time complexity of an individual operator". I am finding that the amortized time complexity of a single operator is $\Theta(1)$ but at the same time the time complexity of a single operator is bigger then that of an amortized time? $\endgroup$
    – imbAF
    May 7 at 13:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.