0
void push(const Type& e){
        if (size() == CAP) {
            CAP = CAP + 100;
            Type * Snew = new Type[CAP];
            for (int i = 0; i < CAP - 100; i++){
                Snew[i] = S[i];
            }
            delete[] S;
            S = Snew;
        }
        TOP++;
        S[TOP] = e;
    }

What is the time complexity of this algorithm and why? I'm looking at it, hoping I'm not wrong, but I think it has linear time (O(n)) complexity due to the presence of a single for loop, and I think every other operation outside of the loop is a constant time operation.

user11892
  • 103
  • 5
  • 1
    You are correct, except for the fact that you don't have any `n` in your code. The time complexity is `O(CAP)`. – barak manos Feb 01 '15 at 06:42
  • Both size() and assignment inside the loop could have any complexity, making the question unanswerable without more information. Also, you probably want to consider amortized cost: the average cost of calling the function if you call it n times. That way you'll see a difference between CAP+100 (average cost O(n)) and CAP*2 (average cost O(1)) assuming the missing code is all O(1). – Paul Hankin Feb 01 '15 at 08:37

2 Answers2

0

It's O(n), all right. Depending on the implementation of new, that might also be O(n) instead of constant (if it's clearing mem or something), but that still makes the whole thing O(n).

Thomas Lane
  • 36
  • 6
0

The complexity is O(n). However, note that most stack implementations double the size of the array, rather than increase it by a fixed amount, in order to achieve amortized constant time. See Constant Amortized Time for a discussion.

Community
  • 1
  • 1
markusk
  • 6,477
  • 34
  • 39