CODEWITHSUNDEEP
algorithmrecurrence
Benjamin Alonso Tan
Benjamin Alonso Tan

Reputation: 33

Set up a recurrence relation for the algorithm’s basic operation count and solve it

Consider the following algorithm

ALGORITHM Find(A[0..n‐1])
    if n ==1 return A[0]
    else temp = Find(A[0..n‐2])
    if temp ≤ A[n‐1] return temp
    else return A[n‐1]

a. What does this algorithm compute?
b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.

Does this algo return A[0],A[0..3],A[0..5],A[0.7],A[0..8], perhaps for n=9? Am I on the right track?

Appreciate if someone could give me along! Thanks!

Upvotes: 1

Views: 4559

Answers (1)

bsd
bsd

Reputation: 2717

This algorithm will recursively calculate the minimum of the given array or list of elements.

For every value of n. You calculate he minimum of all values preceding n(ie. <= n - 1). If the value returned is less than the value[n], you return that value else you return value[n].

The base case is trivial when you have only one element. You return that value as the minimum.

Upvotes: 1

Related Questions