Simple log question for algorithm

**Pan** · May 28th 2009, 01:21 PM

I'm terrible with logs (just can't get my head around them).

The question is about big-O notation but the part I don't understand is about logarithms.

I've been told the following:
$\log_3 N = O(\log_2 N)$ because $\log_3 N = \log_3 2 \times \log_2 N$ .

I don't understand why. Can someone go over the simple rules of why that is (the bit after "because")?

And isn't the implication of that, that any $\log_b N$ will be $O(\log_2 N)$

**skeeter** · May 28th 2009, 01:53 PM

Originally Posted by Pan

I'm terrible with logs (just can't get my head around them).

The question is about big-O notation but the part I don't understand is about logarithms.

I've been told the following:
$\log_3 N = O(\log_2 N)$ because $\log_3 N = \log_3 2 \times \log_2 N$ .

I don't understand why. Can someone go over the simple rules of why that is (the bit after "because")?

And isn't the implication of that, that any $\log_b N$ will be $O(\log_2 N)$

$\log_3{2} \cdot \log_2{N} =$

change of base for the 2nd factor ...

$\log_3{2} \cdot \frac{\log_3{N}}{\log_3{2}} = \log_3{N}$

**Pan** · May 28th 2009, 02:15 PM

Originally Posted by skeeter

$\log_3{2} \cdot \log_2{N} =$

change of base for the 2nd factor ...

$\log_3{2} \cdot \frac{\log_3{N}}{\log_3{2}} = \log_3{N}$

If you had $log_b{N}$

Can it be made equal to $\log_b{c} \cdot \log_2{N}$ , where $c$ is just some number that doesn't change.

In other words, any log can be made so that the dominant factor (for large N) is a base 2 log.

Thread: Simple log question for algorithm

LinkBack

Thread Tools

Display

Simple log question for algorithm

Similar Math Help Forum Discussions

Simple primality testing algorithm

Simple question on EM algorithm

Simple algorithm for errors-in-variables problem?

compiling a simple ranking algorithm

Algorithm Question

Search Tags