0 
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.

Improve this question
5
  • 1
    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. Commented Jan 14, 2022 at 11:20
  • 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... Commented Jan 14, 2022 at 11:21
  • 1
    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. Commented Jan 14, 2022 at 12:06
  • @BMW BOI, Will you agree, if the solution will be in C++? Commented Jan 14, 2022 at 12:12
  • 1
    @BMWBOI: Not sure why you do size +=1 Commented Jan 15, 2022 at 1:23

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.