Big Big O

Computer Science Level 1

def find_max(Arr):
    max = 0
    for num in Arr:
        if num > max:
            max = num
    return max

The above code runs in $\text{\_\_\_\_\_\_\_\_\_\_}$ .

This problem is a part of the set: Efficient Algorithms .

O(\log n)

O(n)

O(1)

O(n\log n)

1 solution

David Orrell
Jan 31, 2017

The algorithm is finding the maximum value in the array by starting with a value of zero for the variable 'max'. It scans through each element of the array in turn, comparing it with the current value of the variable 'max', changing the value if at any point a new maximum is found. Each number in the array is compared with 'max' once. Therefore assuming that each comparison takes equal time, the upper bound on the computing time is O(n), since there is an intuitive proportionality between number of elements and computing time.

Big Big O

This problem is a part of the set: Efficient Algorithms .

1 solution

0 pending reports