2.2 Runtime Analysis

Question 1

What is running time complexity of Insertion sort (best and worst cases)?

Answer 1

Best: n - 1
Worst: (n^2 - n) / 2

Question 2

How do you calculate the runtime complexity of mergeSort

Answer 2

n * height of the tree

Question 3

How do you calculate the height of the tree in MergeSort

Answer 3

Log(2)N

Question 4

What is the runtime complexity of MergeSort

Answer 4

N * Log(2)N

Question 5

Draw the symbols for a quadratic function for:
grows at most
grows at least
grows exactly
grows slower than
grows faster than

Answer 5

Question 6

Order these by asymptotic growth:
n^3
1
sqrt(n)
nlogn
n
n^2
2^n
logn

Answer 6

1
logn
sqrt(n)
n
nlogn
n^2
n^3
2^n

Question 7

Worst case, average and best case runtime complexity for insertion sort

Answer 7

Worst: O(n^2)
Average: O(n^2)
Best: O(n)

Question 8

Worst case, average and best case runtime complexity for MergeSort sort

Answer 8

O(nlogn)

Question 9

Worst case, average and best case runtime complexity for HeapSort sort

Answer 9

O(nlogn)

Question 10

Is InsertionSort stable? If there are 2 1’s in the array will the first 1 always stay before the second 1?

Answer 10

Yes

Question 11

Can insertion sort be done in situ (using only the array you were given and no extra space)

Answer 11

Yes