'How do I calculate the time complexity of this recursive function which halves the input value or halves it and then adds the input value?
I am having difficulties determining the time complexity of the code below:
int func(int n) { // n > 0
if (n < 2) {
return 1;
} else if (n % 2 == 0) {
return func(n / 3);
} else {
return func(n / 3) + n;
}
}
I have attempted to approach this question using Master Theorem, so I have tried to break it down into:
n = size of input
a = number of sub-problems in the recursion = 3
n/b = size of each sub-problem
f(n) = cost of the work done outside the recursive call
However, I am struggling to understand how to determine the size of each sub-problem and f(n) - the cost of the work done outside the recursive call. At the moment I am just assuming that we take the greater time complexity of the if/else statement so the time complexity would be O(logn).
Also, does the '+ n' in the else statement affect the time complexity of this function?
Any help to understand this would be greatly appreciated!
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
