Finding the complexity of the given algorithm-CodePudding

Hi I have no idea to calculate the complexity. So if any one help me find the answer it will be great. ( Also try to write how you calculated it)

Find out the complexity of the following algorithm:

function min (X1, X2…………Xn)
  min = X1;

  for i = 2 to n 
    if (min > Xi) then 
      min = Xi;

CodePudding user response：

Let's start from timings:

function min (X1, X2…………Xn)
  min = X1;             # const_1
  
  for i = 2 to n        # n - 1 times 
    if (min > Xi) then  #   const_2
      min = Xi;         #   const_1 (if min > Xi), 0 (if min <= Xi)

So for the worst (when X1..Xn sorted in descending order) case we have execution time T

T = const_1   (n - 1) * (const_2   const_1)

For the best case (when X1 is the minimum)

T = const_1   (n - 1) * (const_2)

We can combine these cases together and have

T = const_1   (n - 1) * (const_2   p * const_1)

where p - some value in 0..1 range (0 - best, 1 - worst case)

In any case we have a linear formula for execution time T

T = A   n * B

where A and B some constant values. Or for complexity O(T):

O(T) = O(A   n * B) = O(A)   O(B * n) = O(B * n) = B * O(n) = O(n)