2

I've been told that the following code has an efficiency O(1):

void mystack::Pop_element()
{
    assert ( nelem > 0 );

    nelem--;

    if ( nelem < reserved / 4 ){

        Resize ( reserved / 2 );

    }
}

But I don't really understand why, since Resize has an efficiency O(n) (that is a fact, we aren't supposed to know the code inside Resize). So, shouldn't the whole code have O(n) efficiency as well?

Zasito
  • 281
  • 1
  • 7
  • 17

1 Answers1

3

The complexity of the code is O(1) except in very rare cases.

The idea is that when you (the programmer) want to use the stack, you initialize the stack to have sufficient space "almost" all the time. Then Resize is never called, or at least called very rarely.

Being pedantic over special cases, it's possible to refer to this as amortized constant time, because the time complexity is constant except in exceptional circumstances.

See also: Constant Amortized Time

Community
  • 1
  • 1
Alex Walker
  • 2,337
  • 1
  • 17
  • 32
  • The last sentence could do with some rewriting, the point of amortized constant times is that the cost over a large sequence of operations grows linearly with the number of operations, so each operation is approximately constant (total cost/total operations = K), even if some operations might be more and some less. The important difference is that the frequency of the expensive operation cost must be inversely proportional to the associated cost so that `cost(x)*freq(x)` yields a constant factor. – David Rodríguez - dribeas Oct 31 '13 at 18:43