5.1 Linear Time Sorting

Question 1

What is the number of permutations of n objects

Answer 1

n!

Question 2

What is the height of binary tree with l leaves

Answer 2

at least log(L)

Question 3

What is the height of a decision tree

Answer 3

at least log(n!)

which is actually

at least log((n/2)^n/2)

which is actually

nLog(n)

Question 4

What is the lower bound for all comparison based sorting algorithms (run time complexity)

Answer 4

nLog(n)

Question 5

What variables are needed for CountingSort?

Answer 5

A - input array
Z - output array
C - work array (where we count)
k - limit of the universe: {0, … ,k}

Question 6

Is CountingSort in situ?

Answer 6

No

Question 7

Is countingSort stable

Answer 7

Yes

Question 8

What is the runtime complexity for CountingSort and what are the condition

Answer 8

O(n + k) when sorting numbers {0, … ,k} we have to set the restriction k

Question 9

What is radixSort?

Answer 9

Uses counting sort but goes digit by digit

Question 10

What is the runtime complexity for Radixsort and what are the condition

Answer 10

O(s * (n+b)) where b = n + k in CountingSort and s is how many digit the numbers are