What's the space complexity of this function and why is it O(log n)?

What's the space complexity of this function and why is it O(log n)?
int f(int n) {
if (n

Other urls found in this thread:

geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
twitter.com/NSFWRedditVideo

Represent the stack as a tree, then you'll see why the space used is log n

not op but what if it was nonrecursive?

>Represent the stack as a tree
liek dis?

my prof said the iterative version is constantinople time

Yes

Then what?

Yes

...

Looks like n + 2(n-1) + 4(n-2) + 8(n-3) + ...

obvious memoization could reduce this to simply n

holy shit you're fucking dense. what's next, ask Sup Forums for help with your long division homework?

Is O(1) you fucking brainlets. The input is limited to a 32 bit signed integer.

>What's the space complexity of this function
It's O(n). Calling f(317) involves 317 nested stack frames.

But it's not. It's O(n). You need n stack frames in order to get to the base case.

aka the total number of stacks is Sum(2^k, k=0 to k=n-1)

cant you use cool simd tricks to get the n-th fib number rly fast

This is just like the recursive fibonacci implementation, which has a space complexity of O(n).

Subtle troll attempt.

It's O(n). The two recursive calls don't operate in parallel, and the max depth is n.

You won't be able to do f(317) returning an int. It doubles every iteration, so you're dealing with 2^317, which is ~gogleplex territory.

>what is integer overflow

cuz it's a DE and you automagically solve for it anyway

Okay. But that has no bearing whatsoever on the space complexity.

Recursive call begin execute as generative tree post order.

geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

N value build 2^N nodes but you need at max just N memory to travel tree

>why is it O(log n)?
It's not.
>The two recursive calls don't operate in parallel,
Even if they did, it still would be O(n).

Depends on how you analyze it. Assuming no memoization, and that each function call occupies some constant C + the amount occupied by both recursive calls until both exit (ie, assume they can all be alive at once), then for an input of n, 2^(n-1) leaf calls and so 2^n - 1 living calls at once worst case, which is a member of O(2^n).