9 Replies - 2572 Views - Last Post: 08 February 2013 - 09:28 AM

#1 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3178
  • View blog
  • Posts: 9,635
  • Joined: 05-May 12

In computer science, does 'log n' automatically imply base 2?

Posted 06 February 2013 - 08:36 AM

In computer science, does 'log n' automatically imply base 2?

I'm asking this silly question because I found myself trying to recall the formula for the height of a complete binary tree, to help answer the question in C++ forum about QuickSort overflowing its stack. Since it's been many years since college, all I could recall was that tree operations typically cost O(log n), and this was based on the average depth/height of a tree. So just doing a quick search without actually reading the rest of text, I found the formula the the height of a complete binary tree was log(n + 1) where n is the number of nodes.

Hitting numbers in a calculator was giving me odd results though. For example, a binary tree with height of 3, will have 23-1 == 7 nodes. But log(7+1) == log(8) ~= 0.903. Not even close to 3. Trying ln(8) ~= 2.07, close but not yet there. It was only after I tried log2(8) did I get the correct answer.

If somebody offers a choice between algorithms that are O(log n) vs O(ln n) vs O(log5 n), should I assume it is log2 n, or stop and ask whether it is log10 n?

Is This A Good Question/Topic? 0
  • +

Replies To: In computer science, does 'log n' automatically imply base 2?

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1132
  • View blog
  • Posts: 2,490
  • Joined: 05-May 05

Re: In computer science, does 'log n' automatically imply base 2?

Posted 06 February 2013 - 08:40 AM

From my experience, it's usually log base 2 when dealing with CS theory. Binary trees suggest log base 2 as well, since each node splits into two.
Was This Post Helpful? 1
  • +
  • -

#3 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7301
  • View blog
  • Posts: 12,158
  • Joined: 19-March 11

Re: In computer science, does 'log n' automatically imply base 2?

Posted 06 February 2013 - 08:50 AM

"Usually base 2" is my experience as well, but with a caveat: CS folks are pretty cavalier about this, and will use whatever's convenient. Usually when they talk about Big-O, they're just concerned with getting the order of growth right, and once they get there, they're not trying to get numbers that compare well.

In your tree problem, it's not hard to see how the number of branches is the correct base to use - again, the fairly careless assumption is made that because it can be derived it need not be stated.
Was This Post Helpful? 2
  • +
  • -

#4 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2017
  • View blog
  • Posts: 3,046
  • Joined: 21-June 11

Re: In computer science, does 'log n' automatically imply base 2?

Posted 06 February 2013 - 09:00 AM

Note that in Big-Oh the base of a logarithm doesn't matter. It is not meaningful to say an algorithm runs in O(log5 n) time because the base of a logarithm is equivalent to a constant factor - an algorithm that takes log10 n steps is still in O(log5 n), so the 5 is just a red herring.
Was This Post Helpful? 4
  • +
  • -

#5 lordofduct  Icon User is online

  • I'm a cheeseburger
  • member icon


Reputation: 2506
  • View blog
  • Posts: 4,615
  • Joined: 24-September 10

Re: In computer science, does 'log n' automatically imply base 2?

Posted 06 February 2013 - 09:03 AM

As a math major, this angers me greatly.

Numeric bases should never be implied.

I feel for ya OP. I feel for ya.
Was This Post Helpful? 1
  • +
  • -

#6 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 337
  • View blog
  • Posts: 730
  • Joined: 27-June 09

Re: In computer science, does 'log n' automatically imply base 2?

Posted 06 February 2013 - 10:27 AM

It's not really implied, it just doesn't matter. In CS I have never used logs outside of the context of big-O and as sepp pointed out, the difference in base is just a constant factor. So, it is dropped.

I first learned big-O in calculus and it was the same concept there. O(log(n)) and O(ln(n)) were always equally correct answers.
Was This Post Helpful? 0
  • +
  • -

#7 lordofduct  Icon User is online

  • I'm a cheeseburger
  • member icon


Reputation: 2506
  • View blog
  • Posts: 4,615
  • Joined: 24-September 10

Re: In computer science, does 'log n' automatically imply base 2?

Posted 06 February 2013 - 10:42 AM

I wasn't talking in the case of Big-O where the base is inconsequential. I agree that's not a necessary thing.

But if it's a formula for calculating the length or size of something (such as in OP's case), that's not a generic base that isn't necessary. It's a required base, because if you change the base, the formula outputs a different result.

(note, OP referenced two different log operations, one was a Big-O notation, the other was calculating the height of a binary tree... the ladder of which is the one that is implied, and IMO should never be implied. I didn't feel I had to get into generalized exceptions like that of Big-O as jon.kiparsky and sepp2k did such wonderful jobs at making that distinction)

This post has been edited by lordofduct: 06 February 2013 - 10:46 AM

Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3178
  • View blog
  • Posts: 9,635
  • Joined: 05-May 12

Re: In computer science, does 'log n' automatically imply base 2?

Posted 07 February 2013 - 09:12 AM

View Postsepp2k, on 06 February 2013 - 11:00 AM, said:

Note that in Big-Oh the base of a logarithm doesn't matter. It is not meaningful to say an algorithm runs in O(log5 n) time because the base of a logarithm is equivalent to a constant factor - an algorithm that takes log10 n steps is still in O(log5 n), so the 5 is just a red herring.


I had a hard wrapping my mind around this since as computer scientists we make a big deal about how much better O(n2) is over O(n3). The exponents are constant and they seem to matter. e.g. Pick the former over the latter. Why don't they matter when looking at O(log2n) vs O(log3n)?

Anyway, I had to read the quote above several times trying to understand where the constant factor comes until I remembered that: logbn = logdn / logdb. logdb is constant.
Was This Post Helpful? 0
  • +
  • -

#9 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2860
  • View blog
  • Posts: 10,964
  • Joined: 15-July 08

Re: In computer science, does 'log n' automatically imply base 2?

Posted 08 February 2013 - 08:42 AM

As others have said, Big Oh analysis cares simply about order and scale. It cares about how the size or time requirements scale with an increasing dataset size (say n becomes 2n). Logrithmic time, in a lot of cases, is simply called sub-linear or sub-polynomial time, which means that as it scales, it scales logarithmically be a factor. That factor is not always critical in Big Oh.

As to the question of what base to use: In binary trees, use base 2. In trinary trees, use base 3, and so on. Note that this is different than layered trees or other more advanced trees.
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10193
  • View blog
  • Posts: 37,643
  • Joined: 27-December 08

Re: In computer science, does 'log n' automatically imply base 2?

Posted 08 February 2013 - 09:28 AM

A lot of times, polynomial time algorithms are just referred to as polynomial time algorithms. Logarithm curves look the same though, whereas not all polynomial curves look the same.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1