Section 17

Asymptotic notation
Sorting algorithms

Asymptotic notation

Consider the following code fragment:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2 * n; j++) {
        methodA();
    }

    for (int j = 0; j < i; j++) {
        methodB();
    }

    if (i % 2 == 0) {
        methodC();
    }
}
System.out.println();

For each of the following, find the function that expresses the number of times each part of the code is executed for a given value of n, and then determine which growth class each function belongs to. ¹
1. the number of times methodA() is executed
2. the number of times methodB() is executed
3. the number of times methodC() is executed

Sorting algorithms

Answer the following questions about sorting algorithms. If an input array is needed for a trace, use the following unsorted array:

Trace bubble sort on this input array. Count the number of swaps, and then reason about the number of swaps for a given input size, n, using big O notation. ²
Show how Shell sort would create “subarrays” with an initial increment of 3. Then show the action of Shell sort on the array, counting the number of moves, and express the number of moves in terms of the input size, n, using big O notation. ³
Complete a trace of quicksort. Count the number of swaps, then reason about the number of swaps for a given input size, n, using big O notation. Verify your answer using the quicksort tracer class. ⁴
Complete a trace of merge sort, neglecting to show the optimization of using a temporary array for the merge step. Then reason about merge sort’s time and space complexity using big O notation. ⁵

a: The precise formula is n · 2n = 2n². This is O(n²).
b: The precise formula is 1 + 2 + ... + n - 1 = n(n - 1)/2. This is O(n²).
c: The precise formula is ceiling(n / 2). This is approximately n / 2 (only a difference of less than 1 when n is odd), which is O(n). ↩

Here’s the trace of bubble sort. Keep in mind bubble sort’s useful invariant: from right to left, bubble sort finds the final position of a value in the array.

+----+----+----+----+----+----+
| 7  | 39 | 20 | 11 | 16 | 5  |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 20 | 39 | 11 | 16 | 5  |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 20 | 11 | 39 | 16 | 5  |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 20 | 11 | 16 | 39 | 5  |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 20 | 11 | 16 | 5  | 39 |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 11 | 20 | 16 | 5  | 39 |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 11 | 16 | 20 | 5  | 39 |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 11 | 16 | 5  | 20 | 39 |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 11 | 5  | 16 | 20 | 39 |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 5  | 11 | 16 | 20 | 39 |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 5  | 7  | 11 | 16 | 20 | 39 |
+----+----+----+----+----+----+

By tracing, we can see that bubble sort makes 10 swaps on this array, which means (since each swap is three moves) it does 30 moves.

We can reason about the code to see that bubble sort’s worst case number of swaps is O(n²). Note that the outer loop will always run O(n) times. Each time the outer loop runs, the inner loop could make a number of swaps equal to the current value of i, the outer loop’s iterator variable. This means our number of swaps will be equal to 1 + 2 + ... + n - 1 = O(n²). ↩

Here’s the trace of Shell sort.
```
+----+----+----+----+----+----+
| 7  | 39 | 20 | 11 | 16 | 5  |
+----+----+----+----+----+----+
```
Note that the code will find the smallest power of two less than the size of the array, and then subtract one, to find the first value of incr. In this case the first such power of two is 4, so incr starts at 3.
```
+----+----+----+----+----+----+
| 7  | 39 | 20 | 11 | 16 | 5  |
+----+----+----+----+----+----+
```
The first subarray formed by incr here is {7, 11}. 7 and 11 are sorted relative to each other, so we do not start moving elements. We then look at 39 and 16, which are out of order relative to each other, so 39 and 16 switch places.
```
+----+----+----+----+----+----+
| 7  | 16 | 20 | 11 | 39 | 5  |
+----+----+----+----+----+----+
```
20 and 5 are again out of order, so they switch places.
```
+----+----+----+----+----+----+
| 7  | 16 |  5 | 11 | 39 | 20 |
+----+----+----+----+----+----+
```
We have now reached the end of one run of the for loop (the variable i reached arr.length). We then divide incr by 2, so incr is now 1.
```
+----+----+----+----+----+----+
| 7  | 16 |  5 | 11 | 39 | 20 |
+----+----+----+----+----+----+
```
When incr is 1, we proceed exactly as in insertion sort.
- 16 not less than 7.
- 5 is less than 16, so 5 needs to be moved into place:
- 11 is less than 16, so 11 needs to be moved into place:
- 39 is not less than 16.
- 20 is less than 39, so 20 needs to be moved into place:
Experimentally, we see that Shell sort made 16 moves. Recall from lecture that Shell sort will improve insertion sort’s usual O(n²) moves to O(n^1.5). This is reflected by the output of SortCount.java, which shows that insertion sort makes 18 moves. ↩
The output of this trace can be generated using the Quicksort tracer class found above. ↩
Here’s a quick trace of merge sort. I’ll show each pair of subarrays as they are merged, in the order they are merged.
```
+----+----+----+----+----+----+
| 7  | 39 | 20 | 11 | 16 | 5  |
+----+----+----+----+----+----+
```
- The first merge combines {7} and {39}.
- The second merge combines {7, 39} and {20} to produce {7, 20, 39}.
- The third merge combines {11} and {16}.
- The fourth merge combines {11, 16} and {5} to produce {5, 11, 16}.
- The fifth and final merge combines {7, 20, 39} and {5, 11, 16} to produce {5, 7, 11, 16, 20, 39}.
Time Complexity: During the Divide stage, the array is continually split in in half until each subarray contains only one element. During the Merge stage, each level of the recursion involves merging subarrays, which involves iterating through all elements at that level. For each level, the merge step takes O(n) and there are O(log n) levels. Therefore, the overall time complexity is O(n log n).

Space Complexity: For each merge step, a temporary array of size n is created to help with the merging process. Therefore, there is an overall space complexity of O(n). ↩

Last updated on July 21, 2026.