I'm trying to solve question 11.1 in Elements of Programming Interviews (EPI) in Java: Search a Sorted Array for First Occurrence of K.

The problem description from the book:

Write a method that takes a sorted array and a key and returns the index of the first occurrence of that key in the array.

The solution they provide in the book is a modified binary search algorithm that runs in O(logn) time. I wrote my own algorithm also based on a modified binary search algorithm with a slight difference - it uses recursion. The problem is I don't know how to determine the time complexity of my algorithm - my best guess is that it will run in O(logn) time because each time the function is called it reduces the size of the candidate values by half. I've tested my algorithm against the 314 EPI test cases that are provided by the EPI Judge so I know it works, I just don't know the time complexity - here is the code:

public static int searchFirstOfKUtility(List<Integer> A, int k, int Lower, int Upper, Integer Index)
{
    while(Lower<=Upper){

      int M = Lower   (Upper-Lower)/2;

      if(A.get(M)<k)
        Lower = M 1;

      else if(A.get(M) == k){
        Index = M;
        if(Lower!=Upper)
          Index = searchFirstOfKUtility(A, k, Lower, M-1, Index);
        return Index;
      }

      else
        Upper=M-1;
    }

    return Index;
}

Here is the code that the tests cases call to exercise my function:

public static int searchFirstOfK(List<Integer> A, int k) {
    Integer foundKey = -1;
    return searchFirstOfKUtility(A, k, 0, A.size()-1, foundKey);
  }

So, can anyone tell me what the time complexity of my algorithm would be?

CodePudding user response：

Assuming that passing arguments is O(1) instead of O(n), performance is O(log(n)).

The usual theoretical approach for analyzing recursion is calling the Master Theorem. It is to say that if the performance of a recursive algorithm follows a relation:

T(n) = a T(n/b)   f(n)

then there are 3 cases. In plain English they correspond to:

1. Performance is dominated by all the calls at the bottom of the recursion, so is proportional to how many of those there are.
2. Performance is equal between each level of recursion, and so is proportional to how many levels of recursion there are, times the cost of any layer of recursion.
3. Performance is dominated by the work done in the very first call, and so is proportional to f(n).

You are in case 2. Each recursive call costs the same, and so performance is dominated by the fact that there are O(log(n)) levels of recursion times the cost of each level. Assuming that passing a fixed number of arguments is O(1), that will indeed be O(log(n)).

Note that this assumption is true for Java because you don't make a complete copy of the array before passing it. But it is important to be aware that it is not true in all languages. For example I recently did a bunch of work in PL/pgSQL, and there arrays are passed by value. Meaning that your algorithm would have been O(n log(n)).