CODEWITHSUNDEEP
algorithmperformancemathrecursiontime-complexity
ayt_cem
ayt_cem

Reputation: 105

Time Complexity of Recursive Algorithm Array

I have a recursive algorithm like that which computes the smallest integer in the array. 

 ALGORITHM F_min1(A[0..n-1])
//Input: An array A[0..n-1] of real numbers
If n = 1
return A[0]
else
temp ← F_minl(A[0..n-2])
If temp ≤ A[n-1]
return temp
else
return A[n-1]

What I think that the reccurence relation should be

T(n)=T(n-1) + n

However I am not sure about the + n part. I want to be sure in which cases the recurrence is T(n)=T(n-1) + 1 and in which cases the recurrence is T(n)=T(n-1) + n.

Upvotes: 2

Views: 469

Answers (1)

Codor
Codor

Reputation: 17605

The recurrence should be

T(1) = 1,
T(n) = T(n-1) + 1

because besides the recursive call to the smaller array, all computational effort (reading the last entry of A and doing the comparison) take constant time in unit cost measure. The algorithm can be understood as divide-and-conquer where the divide part is splitting the array into a prefix and the last entry; the conquer part, which is a comparison, cannot take more than constant time here. In total, a case where there is linear work after the recursive call does not exist.

Upvotes: 3

Related Questions