Harvard University Asymptotic Notation Worksheet

(a) Rank the following functions in order (non-decresasing) of their asymptotic growth. Next to eachfunction, write its big-Theta value, (ie. write the correct (g(n)) next to each function but you are not
required to prove the big-Theta value).
nalogn
Vlog n+ (log n)?, n log(nº.2n), 10!n!, nº.2 (log n)?, n2n, (2″+n)(Vn+2″), , n(log n)
(log n + 1)
(log n)2 +n
(b) Consider the two sorting algorithms below, which each take as input array A[] indexed from s to
f.
= false
SwapSort1(A, s, f)
swapped = true
while (swapped)
swapped = false
for i= s to f-2
if A[i] > A[i+2]
Swap A[i] and A[i+2]
swapped = true
SwapSort2(A, s, f)
swapped = true
while (swapped)
swapped
for i= s to f-2
if A[i] > A[i+2]
Swap A[i] and A[i+2]
swapped = true
swapped = true
while (swapped)
swapped = false
for i=s to f-1
if A[i] > A[i+1]
Swap A[i] and A[i+1]
swapped = true
=
• Execute SwapSort1 on array A = [7, 6, 5, 4, 3, 2, 1) indexed from s = 1 to f = 7.
• Which of the above two algorithms is correct?. Justify your answer.
• What is the worst-case number of comparisons are made by SwapSort2 when the input array A has
length n and is sorted in reverse order?
• Does your result from above represent the worst-case number of comparisons made by SwapSort2?
Justify your answer.
• Justify that the worst-case runtime of SwapSort2 is of the form T(n) an2 + bn + c for constants
a, b, c.
=