analyze algorithm of finding maximum number in array with n number-CodePudding

def maximum(array):
  max = array[0]
  counter = 0

  for i in array:
      size  =1
      if i>max:
          max=i

  return max

I need to analyze that algorithm which find maximum number in array with n numbers in it. the only thing I want to know how to get Recursive and General formula for Average case of this algorithm.

CodePudding user response：

Not sure what you mean by "Recursive and General formula for Average case of this algorithm". Your algorithm is not recursive. So, how can it be "recursive formula"?

Recursive way to find maximum in an array:

def findMax(Array, n):
    if (n == 1):
        return A[0]
    return max(Array[n - 1], findMax(Array, n - 1))

I guess you want Recurrence relation.

Let T(n) be time taken to find the maximum of n elements. So, for above written code.

T(n) = T(n-1)   1 .... Equation I

In case you are interested to solve the recurrence relation:

T(n-1) = T((n-1)-1)   1 = T(n-2)   1 .... Equation II

If you substitute value of T(n-1) from Equation II into Equation I, you get:

T(n) = (T(n-2)   1)   1 = T(n-2)   2

Similarly,

T(n) = T(n-3)   3
T(n) = T(n-4)   4

and so on..

Continuing the above for k times,

T(n) = T(n-k)   k

If n-k = 0, means n = k. The equation then becomes

T(n) = T(0)   n = 1   n

Therefore, the recursive algorithm we came up with has time complexity O(n).

Hope it helped.