This function looks very close to recurrence of QUick Sort . It is recurrence of Quick Sort ! Just instead of partitioning function, we are calling function which has O(1) time. I.e. Constant
So In best case i will be midpoint then !
T(N) = 2(N/2) +c
T(N) = ϴ(lon 2n)
So best case => Ω((lon 2n)
In The worst case, we will alwyas chose i = 0.
Then it will be like
T(N) = T(1) + T(n-1) + c
It will be ϴ(N) in worst case.