Consider the following function f.

Question

now , the question says , worst case time complexity. So, in the worst case , the inner loop condition is not satisfied , so , won't it be O(n2) ?

Answer 1

Lets trace it,

i=1; then j=i=1 => inside A[ i ] != A[ j ] condition false => Execute 'else' part. Break inner loop

i=1; then j=i=2 => inside A[ i ] != A[ j ] condition false => Execute 'else' part. Break inner loop

repeat unto i's counter i.e., n....Thus, it only executes n times. Hence, O(n)

Answer 2

See, i=1,j=1, in checking a[i]!=a[j] , both i and j are 1, so a[1]!=a[1] is false; it breaks; hence executed once; similarly , for i=2; j starts with 2, comparison fails, it breaks; so only one time the inner loop gets executed for every value of outer loop;

hence O(n)