i need some help for some time and space complexity problems in java

Your analysis of the first case is correct.

The second case is more difficult. You can’t really evaluate the time complexity accurately, because:

  • It’s certainly exponential in n;
  • If you need a tight complexity bound, you have to get the base and exponent exactly right; and
  • You don’t really know how long that allocation takes. In some systems it is O(n), because the memory will be zeroed for security. In some it will be O(n) amortized because a copying garbage collector is in use. In some cases it will be indeterminate because some free list has to be walked.

A safe-ish assumption is that allocation takes O(n), but your prof might expect allocation to be O(1). Usually the difference doesn’t matter, because you use all the memory you allocate. O(1) allocation leads to the recurrence relation T(n) = O(1) + T(n-1) + T(n-2). That is a Fibonacci sequence so the complexity is O(𝞿n), where 𝞿 is the golden ratio.

The space complexity is the total simultaneously allocated memory. Again this depends on implementation details, but we can assume that you are using a garbage-collected language that doesn’t require the memory to be freed, because otherwise you are making a horrible mistake by not freeing it. So…

Since the allocated array isn’t used anywhere, there is no reference to it, so if the language is garbage collected then the space complexity will be O(n), since the array can be garbage collected immediately after it’s allocated.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top