Actually O(2^n) is overshooting it a bit (but still correct, since big-O is an upper bound), it's more like ~θ(1.6^n).
Try to picture a recursion tree. Every node splits into 2, and the depth of the tree is n, so it ends up as about O(2^n).
Similarly, the O(3^n) example, every node splits into 3, and the depth is still n.
But for O(3^n), I'd rather recommend something like this:
someFunction(n)
if (n == 0)
return 1
return someFunction(n-1) + someFunction(n-1) + someFunction(n-1)
Of course this can trivially converted to O(n) by changing the last return statement to:
return 3*someFunction(n-1)
But that's not really the point (one could also calculate the n-th Fibonacci number in O(n)).
Now it's quite easy to evaluate.
There is 1 call for n, 3 for n-1, 3*3 for n-2, 3*3*3 for n-3, etc.
It follows trivially that the running time would be O(3^n).
For the permute
function:
Since you're passing k-1
to the recursive call (not i
), you have 1
call for k, k-1
for k-1, (k-1)(k-2)
for k-2, (k-1)(k-2)(k-3)
for k-3, etc.
So that looks like O((k-1)!)
.
If you were to instead pass i
, you'd have 1
call for k, 1
for k-1, 1+1=2
for k-2, 1+1+2=4
for k-3, 1+1+2+4=8
for k-4, 16
for k-5, etc.
So that looks like O(2^(k-1))
.
Binary tree traversal takes O(n)
, but n
isn't the height of the binary tree, it's the number of nodes. In the Fibonacci example, n
is the height. If we were to consider how long traversing a balanced binary tree will take based on the height, we'd also end up with O(2^height)
, which, from some basic mathematics, ends up as O(n)
.