In the algorithm for sorting a linked list, given below:

Question

```
1 i = 0
2 ptr = start
3 while ptr is not equal to NULL
4 A[ i++] = ptr
5 ptr = ptr->next
6 // sort the array with a sorting algorithm (swap addresses instead of elements);
7 // use A[ i ]->info to look at an element
8 for all i from 0 to n – 2
9 A[ i ]->next = A[ i + 1 ]
10 start = A[ 0 ]
11 A[ n – 1 ]->next = NULL
```
consider the time complexity of the sorting algorithm used on lines 6-7. Why don’t lines 1-5 and lines 8-11 contribute any more to this time complexity?

A. The time complexity of lines 1-5 is O( 1 ) and the time complexity of lines 8-11 is O( 1 ).
B. The time complexity of lines 1-5 is O( lg n ), and the time complexity of lines 8-11 is
O( lg n ); these time complexities must be less than that of the sorting algorithm.
C. Lines 1-5 and lines 8-11 are just “peripheral” lines, that have nothing to do with time
complexity.
D. The time complexity of the sorting algorithm must be at least O( n ), if nothing is known about the elements ahead of time; the time complexity of lines 1-5 is
O( n ), and the time complexity of lines 8-11 is O( n ).

Answer 1

D