Need some help/confirmation for some time and space complexity problems in Java

Question

I want to make sure that my way of working with complexity of space and time is good. I am an IT student and I am working part time and I got this exercise besides my work for a course I am following by the company I'm working for and I wonder if I am getting the complexity thing right or if I am on the wrong track!

I am trying to figure out the time and space complexity of two cases. I already have made some steps and gave it a good try, so down below you will find my thoughts and answers of three different methods/functions in Java code. Scroll down for the exercises.

Case 1:

  public int func1(int n) {

   int total = 0;
     for (int i = 0; i < n; i++) {
      for (int j = 50; j > 0; j--) {
       for (int k = 0; k < j/2; k++) {
        total++;
       }
      }
     }
     return sum;
    }

Time complexity
For time complexity I think the outer loop is O(n), the middle loop is O(1) and the most inner loop is also O(1) because it has nothing to do with the first loop, so am I correct if this is Big O(1 * 1 * n) => Big O(n)??

Space complexity
Space complexity of this one must probably be Big O(1) because there are no new variables instantiated in the loops.. Only the loops itself and the int total = 0. But that has nothing to do with the n aswell. So I gues Space is Big O(1).

Case 2:

  public int func2(int n) {
      if (n > 0) {
      int[] array = new int[n+n];
      return func2(n-1) + func2(n-2);
     } else {
      return 0;
     }
    }

Time complexity
The time complexity of this one is a little harder for me, because of the array in the beginning.. I think because of the recursion in the loop, the complexity matters of the n input, so it is Big O(n) time complexity. But I am not sure if it may be n^2 because of the return double recursion func2(n-1) + func2(n-2).. Am I in the right direction with Big O(n)?

Space complexity
And for the last one of all, I think that the space complexity in this case is 2n, which then is n? Because of every time the function is called, it makes a new array with 2n length, so if n=4 the array is 8 long, and then the next iteration is 6 etc..

So my final answer is Big O(n) for space complexity.

Answer 1

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(𝞿ⁿ), 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.