I recently did a technical interview and was asked for the memory complexity of the following algorithm that I wrote on the whiteboard. To be more specific, if I remember correctly, he was referring to "heap space":
public int[] fib = new int[1000];
public int fibonacci(int i) {
if (i == 0) return 0;
if (i == 1) return 1;
if (fib[i] != 0) return fib[i];
fib[i] = fibonacci(i - 1) + fibonacci(i - 2);
return fib[i];
}
Because he said "heap space", it sounds like he was giving me a clue that he wanted me to give the complexity of the following line of code:
public int[] fib = new int[1000];
I think I remember learning in school that new in Java is like malloc in C, where malloc allocates storage off the heap. Assuming that my memory serves me correctly, let's now go back to my question: what is the memory complexity of this? Was I supposed to say O(1000)? O(n)? Something else?
Thanks!
I think your interviewer wanted to know how well you understood the consequences of the code you wrote. The usual potential memory problem with non-tail-call recursive code is that each recursive call takes up a stack frame, which can't be garbage collected until the call (including all its recursive subcalls) is completed. The stack frames are allocated from the heap, so the recursion can deplete the heap.
Without the memoization shortcut that saves and retrieves the already-calculated fibonacci numbers, the memory complexity would be O(n2): calculating the nth fibonacci number would create a recursive tree of stackframes proportionate to the square of n, as it recalculated the same numbers for different branches of the tree.
But the posted code shouldn't have to calculate any one fibonacci number more than once, and the total number of stackframes will not explode the same way, it would be kept down to O(n) for the worst case, where the array is initially empty. It would be O(1) once the array is populated, since at that point it amounts to a single array lookup.
O(n) seems correct to me. You would not include constants (like O(1000)) in O notation.
By the way, this is the problem I have with recursive functions, its open ended memory complexity. I can not go live with such recursive functions unless I can put limits on the input size.
