0
$\begingroup$

Below I have two algorithms for finding the maximum 2 numbers from an array of numbers of size>=2. n=Size of the array

Algorithm 1:-
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?

$\endgroup$
  • $\begingroup$ The exact time complexity depends on the input. See what happens if the array is strictly increasing or strictly decreasing. $\endgroup$ – Yuval Filmus Feb 17 at 4:02
  • $\begingroup$ "n=Size of the array. Loop through the array, find the index of max number. (n comparisons)". (n-1) comparisons? $\endgroup$ – Apass.Jack Feb 17 at 12:46
  • $\begingroup$ Have you considered the average time-complexity assuming all elements are distinct and each permutation is equally likely? That should be an interesting (and difficult?) exercise. $\endgroup$ – Apass.Jack Feb 17 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.