Below I have two algorithms for finding the maximum 2 numbers from an array of numbers of size>=2. n=Size of the array
1. Loop through the array, find the index of max number. (n comparisons)
2. Swap the last position number with the number present at the index of the max number.
3. Loop through the array excluding the last element, and find the max number. (n-1 comparisons)
4. Swap the last but one position number with the index of 2nd largest number.
5. The max two numbers are now in pos n and n-1.
So the time complexity of the above program is always (n + n-1) ~ 2n.
2nd Algorithm (In python3), a=array
def max_pairwise(a): n = len(a) max1 = 0 max2 = 0 for i in range(0, n): if a[i] > max1: max2 = max1 max1 = a[i] elif a[i] > max2: max2 = a[i] return max1, max2
I know that 2nd algorithm is better than the 1st algorithm as inside of the loop we sometimes make 1 comparison(when the array element is greater than the max1 number) and sometimes 2 comparisons(when the array element is less than the max1 number). So the time complexity has to be between n to 2n comparisons, but how to do I calculate the exact time complexity of the 2nd algorithm?