Algorithm Complexity

$14\mathrm{.}1.$ ID numbers in a particular software application are n$-$digit strings of digits, which we'll be

interpreting as numbers by ignoring leading $0\text{'}$s$-$for example, $021237$ and $000472$ are both $6-$digit

strings of digits. Consider an algorithm that looks at that $n-$digit string of digits, views it as a number $($by

ignoring leading $0\text{'}$s$)$ and then calculates its factorial by multiplying $n(n-1)(n-2)(n-3)cdots(2)(1).$

For example, on the input $000472,$ the algorithm will calculate $472(471)(470)(469)cdots(2)(1),$ doing

$471$ multiplications

a$.$ Calculate an exact expression for the worst$-$case number of multiplications involved, as a

function of $n($remember $n$ is the number of digits$),$ and identify its big$-$ class.

b$.$ Calculate an exact expression for the best$-$case number of multiplications involved, as a

function of $n,$ and identify its big$--$ class.

c$.$ Assuming all n$-$digit strings of numbers are equally likely, calculate

the average$-$case number of multiplications involved, as a function

of $n,$ and identify its big$--$ class.

$14\mathrm{.}2.$ The table at right shows the number of known species in different

major groups of organisms. Suppose you were designing a classifier using

a series of yes$/$no questions to identify a given species. $($The classifier is

going to identify the species, not identify what group it's in$-$e$.$g$.,$ if I have a

raven the classifier is going to ask enough questions to identify that it's

Corvus corax, not that it's a bird. So there are $1,730,725$ possible outputs

for the algorithm.$)$

a$.$ If you wanted your classifier to be optimal, what would be its