How to calculate time complexity of this code?

[bassel27]

What is the time complexity for my code with showing your steps? I tried to figure it out by doing O(T*(n+n+n)) = O(T*n). Am I correct? And any suggestions to make this code more efficient? (Problem here: https://codeforces.com/problemset/problem/1492/B)

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

    vector <int>indeces;
    vector <int>afterIndex;

    while (n != 0) { //o(n)
        //*itr = largest element in the array
        auto itr = find(p, p + n, *max_element(p, p + n));
        int index = distance(p, itr);
        indeces.push_back(index); //push_back index
        afterIndex.push_back(n - index - 1); //push_back number of elements after the index
        //deleting element by decreasing n:
        n = index;
    }

    int i2 = 0;
    int i = indeces[i2];
    while(i2!=indeces.size()){ //let's say it's o(n)
        cout << p[i] << endl;
        i++;
        if (i > indeces[i2] + afterIndex[i2]) {
            i2++;
            if (i2 == indeces.size()) {
                break;
            }
            i = indeces[i2];
        }
    }


    delete[] p;
}
return 0;

[lastchance]

It looks like O(n²), or, if T isn't bounded, then O(T.n²)

But what on earth are you trying to do on line 16? Or, for that matter, in the rest of the code?

[ne555]

to clarify on the order

    while (n != 0) { //the loop executes n times
        //*itr = largest element in the array
        auto itr = find(p, p + n, *max_element(p, p + n)); // O(n) operations
        int index = distance(p, itr); // O(1)
        indeces.push_back(index); // O(1)
        afterIndex.push_back(n - index - 1); //push_back number of elements after the index
        //deleting element by decreasing n:
        n = index;
    }

inside the loop you've got two O(n) operations (find and max_element) and several O(1), so the loop ends being O(n^2)

> And any suggestions to make this code more efficient?
it would be easier if we know what the code is supposed to do
for your running maximum consider this:
max( array[0, n+1) ) = max( max(array[0, n), array[n]) )
in other words, just check if the "new" number is bigger that your current maximum.

[helios]

Am I correct in assuming that line 16 could have been rewritten as

auto itr = max_element(p, p + n);

?

[bassel27]

How do you guys know that the function find() has a time complexity of O(n)?

[lastchance]

@bassel27,
If you have an (unsorted) linear data structure then you have little choice but to check each element one after another to search for something. In the worst case you would have to check n elements (and then you might not find it).

[bassel27]

I've updated the link above because it wasn't working, sorry for the inconvenience. Anyway, I've tweaked my algorithm a bit, but I still get time limit exceeded.

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

int main() {
    int T, n;
    cin >> T;
    while (T--) {
        //inputting p[n]
        scanf_s("%d", &n);
        int* p = new int[n];
        for (int i = 0; i < n; i++) {
            scanf_s("%d", &p[i]);
        }
        
        int i = 0;
        while (n != 0) {
            int i = max_element(p, p + n) - p; //i = index of maximum element
            for (int j = i; j < n; j++) {
                cout << p[j] << endl;
            }
            n = i; 
        }
        
        delete[] p;
    }
    return 0;
}

[ne555]

max_element() is O(n) and you put that inside a loop, take a guess (consider what would be the worst case, how many iterations does the 18--24 loop performs)

[lastchance]

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

const int MAX = 100000;

int main()
{
   int T, n;
   static int p[MAX];

   cin >> T;
   while( T-- )
   {
      cin >> n;
      for ( int i = 0; i < n; i++ ) cin >> p[i];
      vector<bool> S( 1 + n, true );
      int target = n;
      for ( int b = n - 1, a = b; b >= 0; b = a - 1, a = b )
      {
         while( !S[target] ) target--;
         while( p[a] != target ) S[p[a--]] = false;
         S[target] = false;
         for ( int i = a; i <= b; i++ ) cout << p[i] << ' ';
      }
      cout << '\n';
   }
}

[dhayden]

Bassel27, you're asking us to optimize your code but I think the first thing is to explain your algorithm. How does the algorithm solve the problem? Maybe once we understand that we can determine whether the code is bad or the algorithm is fundamentally slow.

[jonnin]

How do you guys know that the function find() has a time complexity of O(n)?

the standard library algorithms all have their complexity given in documentation. Most of them are common sense... how hard is it to find something in a container? Well, the worst containers, you look one item at a time until you find it... O(n).

if nothing else your original is wasteful in its allocation and destruction of P every iteration.
make it once, big enough for whatever you need to put into it, and keep it around recycle it every iteration.
but that is window dressing. I am fairly sure you are using the wrong approach -- you can't loop and find the max every iteration, there has to be a way to avoid that (and I think you have already been shown this a couple of times).

[dhayden]

Your algorithm is still less than optimal. Let's look at the problem.

Anytime you see a decreasing set of numbers, you want to cut the deck at the maximum (left most) number. In other words, with
4 3 2 1
you want to cut it at 4.

In fact, the numbers don't even have to decrease, they just need to be smaller than 4:
4 3 1 2
You still want to cut it at 4.

The only time you add a cut is when you see a larger number:
4 3 1 2 6 5
Here you want to add a cut at 6. So the algorithm to find the placement of the cuts is:

1. Set "highest" to the first number
2. Scan left to right. If you see a number that's less than highest, don't add a cut
3. Otherwise, of you find a number that's greater than highest, add a cut there and set
the number number to highest
4. Repeat at step 2 until you've scanned the whole deck (or found the largest number)

Each time you find a place to cut the deck, remember that location. When you're done, just cut the deck at the remembered locations (last one first) and print the cards from that spot to the last location.

This runs in O(n) time and space.

Example:
6 3 5 8 9 2 4 7 1

Highest = 6 at position 1.
Scan to right until you find a higher number. You find 8 at position 4
Then 9 at position 5.
Since 9 is the largest number, you can stop there.

So the cut points are at positions 1, 4, and 5.
Print cards 5 to 9: 9 2 4 7 1
Print card 4: 8
Print cards 1 to 3: 6 3 5
The resulting output is 9 2 4 7 1 8 6 3 5

[lastchance]

Start at the END of the array.

(1) Search BACKWARDS for the largest unused value (this starts life as n)

(2) Print from there to the last unprinted value (this starts life as the end of the array).

(3) Repeat from (1) until you exhaust the array.


It is easy to keep track of those you have used - e.g. in a boolean array.
@Bassel27's main problem is that he keeps searching for another "highest" and doesn't make use of the fact that there are no repeats. The only thing that he needs to fix is
int i = max_element(p, p + n) - p;
since the maximum element is simply the first one that he hasn't used. Always searching backwards makes for an O(n) overall trial. Searching for maximum element every time is O(n²).