0
$\begingroup$

When the ratio is $1$, why does the efficiency of the algorithm evaluate to $\mathcal{O} \left( n^d \log n \right)$?

The total work done would be:

$T(n) = \mathcal{O}(n^d) (1+1+\cdots+1^k)$

$= \mathcal{O}(n^d) (1)(\log_b n)$

where $n$ is the size of the problem, $d$ the efficiency exponent, $k$ the height of the tree and $b$ the factor the size of the problem is reduced by at each iteration

Therefore wouldn't the efficiency be $\mathcal{O}(n^d) \log_b n$ as opposed to $\mathcal{O}(n^d \log n)$?

  • 0
    No: The MT is a list o$f$ recipes to deduce the asymptotic behaviour of a sequence from a recursion that the sequence satisfies. Your question assumes this step is done and is concerned with the result produced by the MT. As I said, the question is **internal** to the bi$g$-O notation. (But this is no big deal.)2012-05-10

1 Answers 1

1

$\log_b(n) = \log_b(e) \times \log_e(n)$ Hence, it doesn't matter in the big-$\mathcal{O}$ notation.

  • 1
    You can replace$e$above with any constant to get any kind of log you like. $\log_b(n)=\log_b(7)\times\log_7(n),$ for example.2012-05-10