CareerCup

void fn(int n)
{
int d,i=0;
int j=n;
while(i<j)
{
i++;
//d=i*i+(j-.25)*(j-.25)-n*n;
//if(d>0) j--;
}
}

We have O(n) complexity in that case

Then lets assume that d is ALWAYS be positive, than we have O(1/2 n) that is O(n) anyway

I don't think d>0 always.
Necessary condition is i^2 >= n^2 - (j-0.25)^2
if we ignore 0.25, i^2 >= n^2-j^2
base condition is i=0, j=n, where condition won't be true.

Lets assume n=4;

1st Iteration: i=0; j=4
2nd iteration: i=1; j=4
3rd iteration: i=2; j=3 --> as d>0 satisfies here
4th iteration: i=3; j=2

So this is O(n) complexity

even though if we dont care about what the value of d going to be then also time complexity will be O(n) because if d>0 then j will move one move left which will decrease no of move by i.if d<0 then all n move will be done by i

it was a time wasting objective question in that paper.

This is o(n/2)

Big O is about the worst case. Here the worst case is the time where J is never decremented. Therefore, we assume that d is always negative, and we will find an average value.