2
$\begingroup$

Is it possible to simplify

$$\log_3{n} \cdot 2^{\log_3{n}} \cdot n$$

I am actually trying to find the Big-O notation for this equation. But if you don't know what it is, is it possible to simplify this? To something close to

$$n^{\log{3} / \log{1.5}}$$

2 Answers 2

2

$$\log_3{n} \cdot 2^{\log_3{n}} \cdot n = \log_3{n} \cdot n^{\log_3{2}} \cdot n= \log_3{n} \cdot n^{\log_3{2}+1} =\log_3{n} \cdot n^{\log_3{6}}$$

In big O notation, for each $\epsilon >0$, this is $O( n^{\log_3{6}+\epsilon})$.

  • 0
    How did u get from step 1 to 2 ($2^{\log_3{n}}=n^{\log_3{2}}$)? Also I saw but am not familiar with the epsilon part2011-11-15
  • 0
    It is a basic property of the logs: $a^{\log_b(c)}=c^{\log_b(a)}$. To understand why, apply $log_b$ on both sides...2011-11-15
  • 0
    @jiewmeng Also, the epsilon part says that it is not $O( n^{\log_3{6}})$ but it is $O( n^{\alpha})$ for any $\alpha > \log_3(6)$.2011-11-15
0

$$ \log_3{n} \cdot 2^{\log_3{n}} \cdot n =\log_3{n} \cdot 2^{\log_3{n}} \cdot 3^{\log_3{n}}=\log_3{n} \cdot 6^{\log_3{n} }$$