How to calculate the average-case complexity of an algorithm that finds the biggest and second-biggest number?

Question

I'm still struggling to understand how to calculate the average-case complexity of my algorithms - probably due the fact I lack some fundamentals on probability.

I have an algorithm that should find the biggest and second-biggest number. A sample written in JavaScript:

/**
 * @param nums - array of numbers
 * @param n - array length
 */
function findBiggest(nums, n) {
  let biggest = nums[0], biggest2 = nums[1];

  for (let i = 1; i < n; i++) {
    /* Whenever biggest is changed, biggest2 is also 
     * automatically updated.
     */
    if (nums[i] > biggest) {
      biggest2 = biggest;
      biggest = nums[i];
    }

    else if (nums[i] > biggest2 && nums[i] < biggest)
      biggest2 = nums[i];
  }

  return [biggest, biggest2];
}

/**
 * Input: [5, 2, 4, 3, 1]
 * Output: [5, 4]
 */

Best-case scenario

I believe the best-case would be a list ordered in descending order (e.g. [5, 4, 3, 2, 1]), as we wouldn't have to jump into any condition.

So, considering every instruction, the cost would be 2 + 1 + 1(n - 1), being:

• 2 - The first two assignments (biggest and biggest2);
• 1 - The for assignment (i = 0);
• 1(n - 1) - Total number of times the first if condition is checked within the for loop.

Since we ignore constants, we can say the best-case scenario is O(n) (linear complexity).

Worst-case scenario

At the same time, I believe the worst-case scenario would be a list in ascending order (e.g. [1, 2, 3, 4, 5]), as we would have to enter into the first condition N-1 times.

Considering every instruction, the cost would be 2 + 1 + 3(n - 1), being:

• 2 - The first two assignments (biggest and biggest2);
• 1 - The for assignment (i = 0);
• 3(n - 1) - Considering the if check and the two assignments within it.

Since we ignore constants, we can say the worst-case scenario is O(n) (linear complexity).

Please, feel free to correct me if both reasonings above are incorrect. I'm also struggling to understand best-case and worst-case scenarios in some cases.

However, I don't know how to proceed to calculate the average-case. I can't even imagine what would be the input for the average-case scenario. I know it may require some probability theory, but I don't know how to even start considering it.

1. What input could be considered valid for the average-case scenario?
2. How to calculate the average-case time complexity?

Answer 1

The average case requires no calculation here; it is also linear time, O(n), because the average case must always be between the best and worst cases.

If the average were better than O(n) then it would be better than the best case, and if the average were worse than O(n) then it would be worse than the worst case. Both would be contradictions.