func3(int n) {
for (int i = 1; i<n; i++)
System.out.println("*");
if (n <= 1)
{
System.out.println("*");
return;
}
if(n % 2 != 0) //check if odd
func3(n - 1)
func3(n / 2);
return;
}
I need to calculate the complexity of this algorithm, how can i do it when i have for in my code and 2 calls to func3?
The bit pattern of n is very helpful in illustrating this problem.
Integer division of n by 2 is equivalent to right-shifting the bit pattern by one place, discarding the least significant big (LSB). e.g.:
binary
----------------------
n = 15 | 0000 1111
n / 2 = 7 (round down) | 0000 0111 (1) <- discard
Therefore:
The best case is when n is a power-of-2, i.e. func3(n - 1) is only called once at the end when n = 1. In this case the time complexity is:
T(n) = T(n/2) + O(n) = O(n)
What is the worst case, when func3(n - 1) is always called once in each call to func3? The result of n / 2 must always be odd, hence:
All significant bits of n must be 1.
This corresponds to n equal to a power-of-two minus one, e.g. 3, 7, 15, 31, 63, ...
In this case, the call to func3(n - 1) will not yield another call to the same function, since if n is odd then n - 1 must be even. Also, n / 2 = (n - 1) / 2 (for integer division). Therefore the recurrence relation is:
T(n) = 2 * T(n/2) + O(n) = O(n log n)
One can obtain these results via the Master theorem.
T(n/2) comes from the recursive call f(n/2) on the penultimate line. Note that because n is odd, there is also a recursive call f(n-1), from the line just before. From there will be a call to f((n-1)/2), and as explained by meowgoesthedog (nice explanation btw) n is odd, n/2 = (n-1)/2; hence you have two calls to f(n/2) overall. Note that when you are in the recursive call f(n-1), n-1 is even so f(n-2) won't be called.