Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$?

share|improve this question
    
The title is misleading, it seems the OP is concerned with (some misconceptions concerning) the big-O notation. –  Did May 10 '12 at 5:54
    
The Master theorem is a theory regarding big-O notation... My question is regarding a conclusion of the Master's theorem making the title valid. –  user26649 May 10 '12 at 11:45
    
No: The MT is a list of 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 big-O notation. (But this is no big deal.) –  Did May 10 '12 at 12:41

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
This might be a stupid question, but what's $e$? Is it some constant in the efficiency equation or is it Euler's number $e$? –  user26649 May 10 '12 at 3:27
    
@FarhadYusufali $e$ is the Euler's constant. I should have mentioned it in the post i.e. $\log_e(n)$ is the natural logarithm of $n$. –  user17762 May 10 '12 at 3:28
    
Sorry, but I'm not to familiar with the properties of natural logs. Would it be possible to provide an explanation without them? Or are they a necessary part of the explanation? –  user26649 May 10 '12 at 11:50
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. –  Charles May 10 '12 at 13:27
    
@Charles Thank You! –  user26649 May 10 '12 at 14:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.