## Lecture 35 - 04/17

### Sorting IV - Algorithmic Bounds

• What is the theoretical bound on a sorting algorithm?
• Let there be some Ultimate Comparison Sort (UCS)
• We know the upper bound on UCS is O(NlogN)$O(N\log N)$, as there are algorithms such as merge sort that exist that have this worst case runtime
• We know the lower bound on UCS is at least Ω(N)$\Omega(N)$, as we have to go through each of our N$N$ elements once at least
• Question: how tight can we make these bounds?

#### Aside: Sorting boxes

• Let us have three boxes, which contain either a puppy (lightest), cat (medium weight), or dog (heaviest)
• The only way we can tell what animal is in which box is by weighing two boxes against each other on a scale
• How many times do we need to use the scale to determine for sure what animal is in each box?
• We can analyse this with a binary decision tree, as shown below:
• This tree shows that for N=3$N=3$ elements, at most three comparisons tells us the order
• What about for N=4$N=4$ elements?
• If N=4$N=4$, there are N!=4!=42$N!=4!=42$ possible permutations
• Putting these permutations in a binary decision tree gives a structure of height lg(24)=log2(24)5$\lg (24)=\log_2(24)\approx5$
• The height of the decision tree (we round up) tells us the number of comparisons needed, so for N=4$N=4$, we need at most 5$5$ comparisons
• Generalize, how many comparisons for N$N$ elements?
• We have N!$N!$ permutations, and the height of the decision tree for these permutations tells us the number of comparisons we need
• Thus the number of comparisons for N$N$ elements has the lower bound Ω(lgN!)$\Omega(\lg N!)$
• Connection to sorting: comparing the animals is exactly analagous to comparing the elements of a sequence to sort, and thus the upper bound on number of comparisons to determine the order of N$N$ elements is also the upper bound on the number of operations to sort N$N$ elements

#### Math to get Equivalent Lower Bound

• We will now derive an equivalent expression for Ω(logN!)$\Omega(\log N!)$
• First we want to show N!Ω(N2N2)$N! \in \Omega(\frac{N}{2}^{\frac{N}2})$
• This is equivalent to saying N!N2N2$N! \geq \frac{N}{2}^{\frac{N}2}$
• This is quite obvious: 10!=1098765...1$10! = 10*9*8*7*6*5*...*1$
• 55=55555$5^5=5*5*5*5*5$
• The N!$N!$ term is clearly larger, which shows this expression
• Now given the first expression, show log(N!)Ω(NlogN)$\log(N!) \in \Omega(N\log N)$
• We have that N!N2N2$N! \geq \frac{N}{2}^{\frac{N}2}$
• Taking logarithm of both sides gives: log(N!)N2log(N2)$\log (N!) \geq {\frac{N}2}\log(\frac{N}{2})$
• Discarding coefficients and constants, we have: log(N!)Nlog(N)$\log (N!) \geq N\log(N)$
• This shows that log(N!)Ω(NlogN)$\log(N!) \in \Omega(N\log N)$
• Now, we want to show Nlog(N)Ω(logN!)$N\log(N) \in \Omega(\log N!)$
• log(N!)=log(N)+log(N1)+log(N2)+ ... +log(1)$\log(N!) = \log(N) + \log(N-1) + \log(N-2)+~...~+\log(1)$
• Nlog(N)=log(N)+log(N)+log(N)+ ... +log(N)$N \log (N) = \log(N) + \log(N) + \log(N)+~...~+ \log(N)$
• As the latter is bigger than the former, we have that Nlog(N)Ω(logN!)$N\log(N) \in \Omega(\log N!)$
• We have now shown that log(N!)Ω(NlogN)Nlog(N)Ω(logN!)$\log(N!) \in \Omega(N\log N) \wedge N\log(N) \in \Omega(\log N!)$
• This implies that both functions grow at the same rate! More formally:
• log(N!)Θ(NlogN)$\log(N!) \in \Theta(N\log N)$
• Nlog(N)Θ(logN!)$N\log(N) \in \Theta(\log N!)$
• Thus: Θ(NlogN)=Θ(logN!)$\Theta(N\log N) = \Theta(\log N!)$

#### Theoretical Bound on Sorting

• From the first section above, we have that the upper bound on some ultimate sort UCS is O(NlogN)$O(N\log N)$
• In the second section, we showed that the lower bound is Ω(N!)$\Omega(N!)$
• We just showed in the third section that the lower bound is equivalent to Θ(NlogN)$\Theta(N\log N)$
• Thus UCS is both upper bounded and lower bounded by Θ(NlogN)$\Theta(N\log N)$
• Thus a sorting algorithm can't asymptotically be better than Θ(NlogN)$\Theta(N\log N)$
• Next lecture: how to sort in Θ(N)$\Theta(N)$ time (not impossible, we just can't compare every element)

#### Misc.

• Unrelated to rest of lecture
• How do we get random numbers?
• Record random stuff, like room noise or various waves of light
• System clock can also be used, but issue of poor granularity; used more often as a random number seed
• Best approach: rely on pseudorandomness
• Example: multiplicative overflow
• Crude random number generator: start from some random number seed, and multiply the number repeatedly by a constant again each time we want to generate the next random number
• Works because integers have a fixed size, so when we go over the integer is truncated and we get pseudorandomness
• This is a very crude algorithm, but it represents the basic idea