Question

Bubble sort (on an array) N items. This has an AVERAGE case time complexity of...

a. O(1)
b. O(log N)
c. O(N)
d. O(N²)

Answer 1

The average case time complexity of Bubble Sort is O(N^2) in the subject of Computers and Technology at the High School level.

Step-by-step explanation:

The subject of this question is Computers and Technology and the grade level is High School.

In Bubble Sort, the average case time complexity is O(N^2), meaning it takes a time proportional to the square of the number of elements in the array. This occurs when the array is not already in sorted order, and each element needs to be compared with every other element multiple times.

For example, let's consider an array of N = 5 elements: [4, 2, 1, 5, 3].

1. In the first pass, the largest element '5' is bubbled to the end of the array.
2. In the second pass, the second largest element '4' is bubbled to its correct position.
3. In the third pass, the third largest element '3' is bubbled to its correct position.
4. In the fourth pass, the fourth largest element '2' is bubbled to its correct position.
5. In the fifth pass, the smallest element '1' is bubbled to its correct position.

This process requires a total of N-1 passes, resulting in a time complexity of O(N^2).