InterviewBit Problems   AMORTIZED2 : Solved


About the AMORTIZED2 : Solved category (1)
Why O(n), my solution (2)
In the first loop, its ++i so i starts with 1 and and in while loop j starts with 0 hence arr[i]>arr[j] no matter what the value of n is. Hence complexity: O(n) (6)
J is outside the for loop (1)
My Explanation of the Solution (1)
How is it o(n)? What about the inner while loop? (8)
Reason for the correct answer: O(n) (1)
Funny.. j++ cannot be executed, so for each i , only one comparison is made (1)
In the first look, the time complexity seems to be O(n^2) due to two loops. But, (1)