Is my application of master theorem correct?

Question

function Sum(A,left,right):
 if left > right:
  return 0
 else if left = right:
  return A[left]
 mid = floor(N/2)
 lsum = Sum(A,left,mid)
 rsum = Sum(A,mid+1,right)
 return lsum + rsum

function createB(A,N):
 B = new Array of length 1
 B[0] = Sum(A,0,N-1)
 return B

I need to derive the theta notation for the worst-case and best-case using master theorem

Comparison with master theorem: T(N) 2T(N/2) + O(1), T(N) = a*T(N/b)+f(N) a = 2, b = 2, f(N) = O(1), d = 0

Applying master theorem: if d < logba then T(n) = (n logba) 0 < log22 = 0 < 1 so T(n) = (n logba)

I got Theta(N) from master theorem. Though im unsure if that is only worst case or also best case as the base case of the Sum function has runtime of O(1).

Answer 1

This algo fulfills the first case of the Master Theorem where c = 1 and

T(n) = Theta(n^1) = Theta(n)

so your conclusion is right. Cost of single function call is O(1) due to constant number of operations - none of them depends on input size.

In layman therms, time of this divide-and-conquer recursive approach is the same as time of linear loop sum algorithm. There are n additional subdivisions steps which don't change asymptotics (linear approach has own costs for loop organisation, with the same linear asymptotic time)

There are no the worst and the best cases.