CODEWITHSUNDEEP
c++algorithmperformancetime-complexitybig-o
bassel27
bassel27

Reputation: 31

Working out the time complexity of this code

What is the time complexity for my code with showing your steps? I tried to figure it out by doing O(T+n+n^2+n) = O(T+2n+n^2) = O(n^2). Am I correct?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int T,n, nClone;
    cin >> T;
    while (T--) { //O(T)
        //inputting p[n]
        scanf_s("%d", &n);
        nClone = n;
        int* p = new int[n];
        for (int i = 0; i < n; i++) { //O(n)
            scanf_s("%d",&p[i]);
        }

        vector <int>pDash;

        while (n != 0) { //O(n^2)
            //*itr = largest element in the array
            auto itr = find(p, p + n, *max_element(p, p + n));
            for (int i = distance(p, itr); i < n; i++) {
                pDash.push_back(p[i]);
            }
            
            n = distance(p, itr);
        }
        for (int i = 0; i < nClone; i++) { //O(n)
            printf("%d\n", pDash[i]);
        }
        delete[] p;
    }
    return 0;
}

Upvotes: 0

Views: 74

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186688

Rules of thumb for complexity arithmetics are

  • consequent loops are added: O(loop1) + O(loop2)
  • nested loops are multiplied: O(loop1) * O(loop2)

In your case:

  while (T--) { // O(T)
    ..
    // nested in "while": O(T) * O(n)
    for (int i = 0; i < n; i++) { // O(n) 
      ...
    }

    // nested in "while": O(T) * O(n)
    while (n != 0) { // O(n) 
      // nested in both "while"s : O(T) * O(n) * O(n)
      for (int i = distance(p, itr); i < n; i++) { // O(n)
        ...
      }
    }

    // nested in "while": O(T) * O(n) 
    for (int i = 0; i < nClone; i++) { // O(n)
      ...
    }
}

we have:

O(T) * (O(n) + O(n) * O(n) + O(n)) == O(T * n^2)

Upvotes: 2

Related Questions