Recurrence Relation based off Pseudo Code (Time complexity)

Question

Consider the element uniqueness problem, in which we are given a range, i, i + 1, . . . , j, of indices for an array, A, and we want to determine if the elements of this range, A[i], A[i+1], . . . , A[j], are all unique, that is, there is no repeated element in this group of array entries. Consider the following (inefficient) recursive algorithm.

public static boolean isUnique(int[] A, int start, int end) {
   if (start >= end) return true; // the range is too small for repeats

   // check recursively if first part of array A is unique
   if (!isUnique(A,start,end-1) // there is duplicate in A[start],...,A[end-1]
       return false;

   // check recursively if second part of array A is unique
   if (!isUnique(A,start+1,end) // there is duplicate in A[start+1],...,A[end]
      return false;

   return (A[start] != A[end]; // check if first and last are different
}

Let n denote the number of entries under consideration, that is, let n = end − start + 1. What is an upper is upper bound on the asymptotic running time of this code fragment for large n? Provide a brief and precise explanation. (You lose marks if you do not explain.) To begin your explanation, you may say how many recursive calls the algorithm will make before it terminates, and analyze the number of operations per invocation of this algorithm. Alternatively, you may provide the recurrence characterizing the running time of this algorithm, and then solve it using the iterative substitution technique?

This question is from a sample practise exam for an Algorithms class this is my current answer can some one please help verify if im on the right track

Answer:

The recurrence equation:

T(n) = 1 if n = 1, T(n) = 2T(n-1) if n > 1

after solving using iterative substitution i got

2^k * T (n-k) and I solved this to O(2^(n-1)) and I simplified it O(2^n)

Answer 1

Your recurrence relation should be T(n) = 2T(n-1) + O(1) with T(1) = O(1). However this doesn't change the asymptotics, the solution is still T(n) = O(2^n). To see this you can expand the recurrence relation to get T(n) = O(1) + 2(O(1) + 2(O(1) + ...)) so you have T(n) = O(1) * (1 + 2 + 4 = ... + 2^n) = O(1) * (2^(n+1) - 1) = O(2^n).