<!--StartFragment -->
void
fun(
int
n,
int
arr[])
{
int
i = 0, j = 0;
for
(; i < n; ++i)
while
(j < n && arr[i] < arr[j])
j++;
}
In this question the inner loop runs n times at most because j is not initialised for every I. this makes complexity O(n) but wont the outer loop also run n times (incrementing and checking conditions in while) and making the total time complexity to be O(n2)??
<!--EndFragment -->