Most solutions to Exercise 4.4.6 of Intro. to Algorithms 3rd edition say, n*log3(n) = Big omega of (n*lg(n)).
Dose it mean log3(n) is equivalent to log2(n) when we are discussing time complexity of algorithms?
Thanks
Asked
Active
Viewed 7,550 times
7
-
This may not give you a lot of points in your CS exams, but my crude estimate is that anything logarithmic with a base greater than one is pretty good. – zneak May 25 '14 at 22:00
-
4Yes, because `log3(n) == log2(n)/log2(3)`. – Oliver Charlesworth May 25 '14 at 22:00
-
Note that "log2(3)" in Oli Charlesworth's comment is a *constant* -- so it doesn't count in asymptotic complexity analysis, the same way O(42n) is just O(n). – j_random_hacker May 25 '14 at 22:01
1 Answers
9
As far as big-Oh notation is concerned, the base of the logarithms doesn't make any real difference, because of this important property, called Change of Base.
According to this property, changing the base of the logarithm, in terms of big-oh notation, only affects the complexity by a constant factor.
So, yes. In terms of big-Oh notation, log3(n) is equivalent to log2(n).
chrk
- 4,037
- 2
- 39
- 47
-
how about log1.5(n)?. I am trying to solve recurrence of heapify function and I come to the conclusion on log3/2(n). I am not sure it's N or log(n) – Vikas Verma Jan 04 '20 at 09:45