CODEWITHSUNDEEP
algorithmbig-otime-complexity
Stabilo
Stabilo

Reputation: 269

Calculating time complexity of algorithm

How to calculate time complexity of function f?

void f(int n)
{
    if (n <= 1)
       return;
    g(n, n / 3);
}

void g(int n, int m)
{
    int i = 1;
    while (m < n) {
       m += i;
       i++;
    }
    f(n / 2);
}

The answer is sqrt(n), but I don't see how...

Thanks

Upvotes: 2

Views: 134

Answers (2)

吴望龙
吴望龙

Reputation: 66

Let Fn be the time complexity of f(n) and Gn,m be the time complexity of g(n,m).

Gn,m = sqrt(n-m) + Fn / 2

Fn = Gn,n/3 = sqrt(n-n/3) + Fn / 2 = C sqrt(n) + Fn/2

So the answer is sqrt(n).

Upvotes: 0

amit
amit

Reputation: 178521

First, note that the the program can be translated now to a single function program, by inlining g(n,m) in f():

void f(int n)
{
    if (n <= 1)
       return;
    m = n/3;
    while (m < n) {
       m += i;
       i++;
    }
    f(n / 2);
}

The inner loop runs in O(sqrt(n)) iteration, because it starts from n/3, ends with n, and is increased by 1,2,3,... so if we sum it we get:

n/3 + (1 + 2 + ... + i) >= n

We need to solve the above equation to find the final value of i, and we get:

1 + 2 + ... + i >= 2n/3

From sum of arithmetic progression:

i(i+1)/2 >= 2n/3

From the above inequality, we can conclude that indeed i is in O(sqrt(n)).

So, we can denote the complexity as:

T(n) = T(n/2)              +           O(sqrt(n))
        ^                                ^
    recursive step                 syntatic sugar for some function
                                   which is in O(sqrt(n)).

Now, we can see that:

T(n) = T(n/2) + sqrt(n) = T(n/4) + sqrt(n/2) + sqrt(n) = ... =
     = sqrt(1) + ... + sqrt(n/2) + sqrt(n)

And the above sum is in O(sqrt(n))

Upvotes: 4

Related Questions