Exam answer confirmation - Amortized time

问题:

The following method op belongs to a class with two private integer-valued instance variables, n and counter, both of which are initialised to the value zero in the constructor, and subsequently only modified by method op.

public void op()
{
    if(counter<100)
    {
        op1(); //method with O(1) time complexity
        counter++;
    }else {
        op2(); //method with O(n^2) time complexity
        counter = 0;
    }
    n++;
}

Assuming that method op1 has time complexity O(1) , and method op2 has time complexity O(n^2), which of the following best represents the amortized time complexity of method op?

A) O(n)

B) O(n log n)

C) O(1)

D) O(n^2)

E) O(n3)

where the answer to the exam was D. I think it should have been C as from my understanding of amortized time, you count what will occur most of the time. In this situation, the worst case is O(n^2), however most of the time the algorithm will run in O(1). Why is it O(n^2)?

回答1:

When talking about amortized runtime, you can not count what will occur most of the time. To start, how do you even define most of the time? The amortized runtime of an operation can be seen as the average runtime of the operation.

Now to your problem:

For simplicity, I will assume that you wrote if (counter < 99) instead of if (counter < 100). This way, the operation repeats itself after 100 cycles instead of after 101 cycles.

When writing O(...), in the following, I will actually mean Θ(...), because otherwise the answer to your question would be trivial, as everything which is O(1) is also O(n^2).

After calling op() 100 times, the total run time would be 99 + 100^2.
After calling op() 200 times, the total run time would be 2 * 99 + 100^2 + 200^2.
Now let's just forget about those 99 or 2 * 99, as they are dominated by the n^2 values.
So after calling op() n times, the total run time would be something like 100^2 + 200^2 + ... + n^2 (for simplicity, let's assume that n is divisible by 100).

Now I will show that this is in O(n^3).

Let k = n/100

100^2 + 200^2 + ... + n^2
= 100^2 * (1^2 + 2^2 + ... + k^2)
=(*) O(100^2 * k * k^2)
= O(k^3)
= O(n^3)

(*): sum from 1 to k of i^2 is k (k+1) (2k+1) / 6 = O(k^3)

So finally, the average runtime of op() is O(n^3 / n) = O(n^2). Therefore, the amortized runtime of op() is O(n^2).