What will be the time complexity of this program

Question

I am very confuse in calculating time complexity of this program in big O notation.

Here is my code.

def maxMin(arr):
    m = arr[0]
    mi = arr[0]
    for i in range(1,len(arr)):
        if arr[i] > m:
            m = arr[i]
        if arr[i] < mi:
            mi = arr[i]
    return "{0} is Maximum and {1} is Minimum".format(m,mi)

arr = list(map(int,input().split()))
print(maxMin(arr))

O(n) where n is the length of `arr`. It makes a single pass over the array (i.e., the loop). The loop executes n-1 times. That's O(n). — Tom Karzes, Oct 22 '20 at 15:33
Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) What are you confused about? _Be specific!_ [ask] — Pranav Hosangadi, Oct 22 '20 at 16:16

score 0 · Answer 1 · answered Oct 22 '20 at 15:34

0

This algorithm is O(n) in time. It visits each element exactly once, and performs a fixed-length operation on it. The more elements, the more time it takes, in a linear relationship.

The algorithm is O(1) in space. It uses a fixed amount of storage to keep track of the min and max, no matter how big the input is.

answered Oct 22 '20 at 15:34

Mad Physicist

107,652
25
181
264

Doesn't range(..) produce a n-1 sized array for all used indexes? Makink the space complexity be O(n)? – Barry Oct 22 '20 at 16:05
1

@Barry. It produced one in python 2. In python 3, it uses just three integers. – Mad Physicist Oct 22 '20 at 16:07

score 0 · Answer 2 · answered Oct 22 '20 at 15:51

As others have already stated the correct answer, it is just an attempt to make it more clear :

Simulating the run :

input : arr = [1, 2, 3, -4, 0, -1] , n = 6

initialized variables : m = 1, mi = 1

let's start loop for i = 1,

[1, 2, 3, -4, 0, -1] 
    ^^  
    ||
    m mi

so, m is changed to 2, because 2 > 1 (old value of m) but mi remains unchanged (as 1 < 2)

i = 2

[1, 2, 3, -4, 0, -1] 
      ^^  
      ||
      m mi

so, again m changed as above (now m = 3) , but mi remains unchanged.

i = 3

[1, 2, 3, -4, 0, -1] 
          ^^  
          ||
          m mi

so, now m remains unchanged, but mi changed ( as -4 < 1), so mi = -4

i = 4

[1, 2, 3, -4, 0, -1] 
             ^^  
             ||
            m mi

now, m remains unchanged, and also mi remains unchanged.

i = 5

[1, 2, 3, -4, 0, -1] 
                 ^^  
                 ||
                m mi

finally, loop ends with m = 3, and mi = -4.

Hence, each element is visited only once that means in the worst case, it is going to visit till the maximum length of array that is n, that means algorithm is scalable in linear order i.e. 0(n)

What will be the time complexity of this program

2 Answers2