java - Figuring out the efficiency of this method

Question

I have come across while developing my program in Java. I need to figure out how efficient this method is in Big-O notation.

This is what my boss told me:

Making use of a suitable Big-O expression, state and explain in some detail the time complexity of method compute. Your explanation must include a justification for the chosen Big-O expression and make reference to the number of calls to compute at Line 6.

public int compute(int[] array, int first, int last) {
        int result = 0;
        
        if(first < last) {
            result = array[first] + compute(array, first+2, last);
        }
        else if(first < array.length) {
            result = array[first];
        }
        
        return result;
    }

Answer 1

To answer problems like this, it's useful to walk through the code yourself and see what it does. Once you can put the method into regular words, it usually becomes much easier to figure out the efficiency.

What does this method do, then? It adds together every other number in the array from first to last. Examining it closer, we can break the function down into

• The base cases
  • else if (first < array.length) { ... } returns the element at index first, or the constant 0. Since array-indexing is a constant-time operation, this branch executes in constant time.
  • Implicitly, result remains 0 if neither of the above cases are triggered. This is obviously constant-time.
• The recursive case if (first < last). In this case, we end up returning the array[first] added to the recursive result of calling the function with first+2.

Looking at the function, we can see that with each iteration first gets closer by 2 to last, until they touch, at which point the function returns.

So, how many times does this happen? The answer is (last - first) / 2. If first always starts at 0, and last always starts at the last index of the array, then the number of executions will scale linearly with the length of the array. Let's call {the length of the array} n.

The function, thus, executes a constant number of operations O(1), and is called O(n) times. O(1) * O(n) == O(n).