[Solved] an algorithm to find what does it do [closed]

by


This code computes the minimum value present in a subsequence of a sequence A. The subsequence begins at index i and ends at index j. Your algorithm could be translated in english as:

puzzle(A, i, j) :
  if the subsequence has only one element :
    return this element
  min-left is the minimum value present at the first half of the subsequence(it's computed recursively)
  min-right is the minimum value present at the second half of the subsequence(it's computed recursively)
  return the minimum of min-left, min-right

The complexity of this algorithm is obviously lineral(O(N)). But, if you don’t believe me, I will prove it for you using the master theorem(http://en.wikipedia.org/wiki/Master_theorem).

Let T(N) be the recurrence of your algorithm. Then:

T(N) = 2T(N/2) =>
T(N) = 2T(N/2) + Theta(1) =>
T(N) = Theta(N) (from the first case of the master theorem, which states
that if f(N) = O(N^logb a-e), for e>0, then the complexity is Theta(N^logb a),
where a=2, b=2, f(N)=Theta(1), and e=1

solved an algorithm to find what does it do [closed]