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
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)
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).
