-2

i am unable to find the O(1) way to find log of n with any base

even if you can determine O(1) time way to calculate log of n with base 2 ,it would be thank full. the link which i encountered is this http://geeksforgeeks.org/?p=10879 (please read the comments on that). they are saying to calculate the number of zero's in front of a number but how that can be done in O(1) time... again i took help of this site whose link is How To Find The Leading Number Of Zero's In a Number using C but O(1) is big issue for me. any help would be highly appreciated.

Community
  • 1
  • 1
user609306
  • 1,333
  • 6
  • 17
  • 27

3 Answers3

3

You cannot do that in O(1) for arbitrarily large numbers. You need at least O(log(n)) to look at the binary representation of the number once.

If you put a bound on the value of n (e.g. 64 bits), then everything is doable in O(1)! O-notation will not make any real sense in that case.

Mehrdad Afshari
  • 414,610
  • 91
  • 852
  • 789
  • In case of a single integer input, you would even say it’s in O(n) where n is the number of binary digits. – Gumbo Jun 04 '11 at 08:45
1

If I've undertood correctly, you just want to calculate the log of a number n in base b. In that case, use the log() function:

log(n)/log(b)
ninjalj
  • 42,493
  • 9
  • 106
  • 148
0

Depending on your CPU and your compiler you may be able to get log2 in O(1) for integer numbers. See the answers of this this question for example. Finding the left most bit of a binary number is the same as log2.

Community
  • 1
  • 1
x4u
  • 13,877
  • 6
  • 48
  • 58