-1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The page already gives 2 examples. Have you read them? $\endgroup$
    – Watercrystal
    May 4 at 12:28
  • 2
    $\begingroup$ This is not a definition. It is an informal explanation. $\endgroup$
    – Yuval Filmus
    May 4 at 12:40
  • $\begingroup$ The sentence just says that the amortized time is the average time. $\endgroup$
    – Yves Daoust
    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

0

Reset to default

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.