Time complexity of a certain program
- by HokageSama
In a discussion with my friend i am not able to predict correct and tight time complexity of a program. Program is as below.
/*
This Function reads input array "input" and update array "output" in such a way that
B[i] = index value of nearest greater value from A[i], A[i+1] ... A[n], for all i belongs to [1, n]
Time Complexity: ??
**/
void createNearestRightSidedLargestArr(int* input, int size, int* output){
if(!input || size < 1)
return;
//last element of output will always be zero, since no element is present on its right.
output[size-1] = -1;
int curr = size - 2;
int trav;
while(curr >= 0){
if(input[curr] < input[curr + 1]){
output[curr] = curr + 1;
curr--;
continue;
}
trav = curr + 1;
while( input[ output [trav] ] < input[curr] && output [trav] != -1)
trav = output[trav];
output[curr--] = output[trav];
}
}
I said time complexity is O(n^2) but my friend insists that this is not correct. What is the actual time complexity?
