How can I get the cost of this function? I know it is O(√n) but other than trying a lot of n values and getting a pattern I don't know how to find it.
void foo(int n) {
int x = 2;
int y = 1;
while(y <= n) {
y += x;
++x;
}
}
What is result of sum(1,2,3,4,...,t)? it equals:
sum(1,2,3,4,...,t)=(t*(t+1))/2
So x in loop is increased by O(t^2). So the number that while loops will be amortized to O(sqrt(n)), because y is increased by x till it reaches to n.
Look at y values, after x iterations the y value would be:
step 1 2 3 4 x
y= 1+2+3+4+...+x
(1) The loop stops when the y>n which means when 1+2+...+x>n. At this point (when y>n), we iterated x times (yes, the same x in the previous equations!)
(2) We also know 1+2+...+x = x(x+1)/2 = O(x^2)
(1)+(2): The loops stops when x^2>n or after √n iterations.
Let's look at the value of y after i iterations:
y = 2+...+i
The loops ends when y > n, so what you are really asking is at which iteration i does this condition become true?
y > n is really 2+..+i > n. We know that 2+..+i = (n(n+1))/2 -1 so
y>n becomes (i(i+1))/2 > n+1 which solves for i^2 +i > 2n+2.
Should be easy enough to see that i is O(sqrt(n)) from here.
The first value at which the inequality y > n holds is proportional to sqrt(2n+2).
Note that 2+..+i = (n(n+1))/2 -1 because of the famous closed formula sum(1,2,3,...,k) = 1+2+3+...+k = (k(k+1))/2
