analyze algorithm of finding maximum number in array with n number

Question

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.

• user1984: The average, best, and worst case are all the same since the algorithm looks at each and every element once, no matter what. There isn't much to analize. Also a not on using max: it's a built-in function in python, so you better avoid shadowing it.
• user17051256: max() is a built-in function if you would take a look you would realize that max is just variable which is equal to first element of array...
• user1984: That what I'm saying. max in your code is initialized with the first element in the array and tracks the largest so far. This overwrites the built-in max function. It is syntactically correct and works just fine for your code, but it's best practice to not do that. It makes your code less readable/maintanable.
• Vadim Chernetsov: @BMW BOI, Will you agree, if the solution will be in C++?
• Shridhar R Kulkarni: @BMWBOI: Not sure why you do size +=1

Answer 1

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.