CODEWITHSUNDEEP
c++complexity-theory
polmonroig
polmonroig

Reputation: 1027

Function Complexity Analysis

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;
    }
}

Upvotes: 3

Views: 86

Answers (3)

Davide Spataro
Davide Spataro

Reputation: 7482

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

Upvotes: 3

Emadpres
Emadpres

Reputation: 3737

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.

Upvotes: 3

Afshin
Afshin

Reputation: 9173

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.

Upvotes: 3

Related Questions