My text is not exactly straightforward in this section and I'm struggling to figure out how to do this problem:
There isn't anything in the book which explains how to find the number of comparisons and none of the recursion systems have anything like the squared term in it. If anyone can point me in the right direction, I'd be ever so grateful!
All I can do really is eliminate C and E by plugging in 3 to the possible general solutions and eliminating which ones don't match up between general solutions and numbers where I use $3$ for $n$
The only thing I have to guide me in the text is this:
Well one can see that $$T(n)=5^{2^{n-1}}$$ $$\therefore T(3)=5^{2^{3-1}}=5^4=625$$ This comes from realising that the value of $T(n)$ is given by squaring $5$ $(n-1)$ times. So the number $5$ is raised to the power of $2$ $(n-1)$ times. This means that the exponent of $5$ is multiplied by $2$ $(n-1)$ times, so the exponent is then $2^{n-1}$.