Logarithms and Order of Growth

Question

I am bit confused on the application of the logarithm rules when it comes to using them to determine the order of growth.

For example:

$ 2^{\log 2n} + 4n = \Theta(2^n) $
$ 2^{2\log 2n} + 4n = \Theta(n^2) $
$ n\log n + 10n^2 + 5^{\log n} = \Theta(n^{\log 5}) $
$ n^{\log n} + 4^{(\log n)^2} = \Theta(n^{\log n^2}) $

Which logarithm rules apply to the above? How exactly are they solved? And how can I determine the order of growth for these types of questions when doing them in the future?

NB: The log is in base 2

I mean, does it have any specific value, or do you have to find it out? @Zaruya — , Mar 08 '18 at 15:21
@idk no, it doesn't. In this case, determining the order of growth is the part of the expression that grows the fastest. For example, an expression: $ n^4 + 10n^3 + 1000n = \Theta{(n^4)} $ because $ n^4 $ would grow the fastest for large inputs — Zaruya, Mar 08 '18 at 15:30

Jesse Meng · Accepted Answer · 2018-03-08T16:24:27.140

0

Your first rule is incorrect:

For example, the logarithms in computer science are in base $2$. So:

$ 2^{\log 2n} + 4n = \Theta(2^n) $ can be simplified to $$6n= \Theta(2^n)$$ which is false as $6n$ grows slower.

The second rule is proven as follows: $$2^{2 \log_2(2n)}=\left(2^{\log_2(2n)^2}\right)=(2n)^2=4n^2=\Theta(n^2)$$

Proof of third rule:

$n\log(n)$ is insignificant compared to $n^2$. $$5^{\log n}=5^\frac{\log_5(n)}{\log_5(2)}=n^\frac{1}{\log_5(2)}=n^{\log_2(5)}$$ $n^2$ is insignificant compared to $n^{\log(5)}$. Hence we have arrived at our conclusion.

Proof of fourth rule: $$4^{(\log n)^2}=2^{2{(\log n)^2}}=((2^{\log n})^{logn})^2=n^{(\log n^2)}$$ $n^{\log(n)}$ is insignificant compared to $n^{(\log n^2)}$, we have arrived at our conclusion.

Note that these rules all proven with the basic properties of $\log$, such as converting bases. You should sharpen on those fundamentals.

edited Mar 08 '18 at 16:24

answered Mar 08 '18 at 15:33

Jesse Meng

1,310

could you explain how you got your answer? – Zaruya Mar 08 '18 at 15:39
Since it's base 2, then $2^{\log_2{2n}}=2n$ – John Glenn Mar 08 '18 at 15:42
@Zaruya It comes from the basic properties of log. – Jesse Meng Mar 08 '18 at 15:51
@JohnGlenn you are right, it is false. It seems that I made a mistake when writing it – Zaruya Mar 08 '18 at 15:54
However, with that correction in mind, that means the answer should be $ \Theta{(n)} $. Because from 2n +4n, n grows the fastest. – Zaruya Mar 08 '18 at 16:05
@Zaruya Only the first rule is false. I have proven the other 3 rules, please check my edit. – Jesse Meng Mar 08 '18 at 16:19

score 0 · Answer 2 · answered Mar 08 '18 at 15:43

0

The property of the log you need is $2^{\log_2 a}=a$. This might be your definition of the base 2 log, otherwise it is a property you should have proven. So $$2^{\log_2(2n)}=2n\\2^{2 \log_2(2n)}=\left(2^{\log_2(2n)}\right)^2=(2n)^2=4n^2$$

answered Mar 08 '18 at 15:43

Ross Millikan

374,822

Logarithms and Order of Growth

2 Answers2