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?