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: shorturl.at/nouEK)
int T, n;
cin >> T;
while (T--) { //O(T)
//inputting p[n]
scanf_s("%d", &n);
int* p = newint[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;
