Is Big O(logn) log base e?

by

Once expressed in big-O() notation, both are correct. However, during the derivation of the O() polynomial, in the case of binary search, only log2 is correct. I assume this distinction was the intuitive inspiration for your question to begin with.

Also, as a matter of my opinion, writing O(log2 N) is better for your example, because it better communicates the derivation of the algorithm’s run-time.

In big-O() notation, constant factors are removed. Converting from one logarithm base to another involves multiplying by a constant factor.

So O(log N) is equivalent to O(log2 N) due to a constant factor.

However, if you can easily typeset log2 N in your answer, doing so is more pedagogical. In the case of binary tree searching, you are correct that log2 N is introduced during the derivation of the big-O() runtime.

Before expressing the result as big-O() notation, the difference is very important. When deriving the polynomial to be communicated via big-O notation, it would be incorrect for this example to use a logarithm other than log2 N, prior to applying the O()-notation. As soon as the polynomial is used to communicate a worst-case runtime via big-O() notation, it doesn’t matter what logarithm is used.

More Related Contents:

  1. Is log(n!) = Θ(n·log(n))?
  2. The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?
  3. Why can’t decimal numbers be represented exactly in binary?
  4. Computational complexity of Fibonacci Sequence
  5. Time complexity of nested for-loop
  6. How can i produce multi point linear interpolation? [closed]
  7. Turning a cylinder into a sphere without pinching at the poles
  8. How to convert latitude or longitude to meters?
  9. Time complexity of python set operations?
  10. Is list::size() really O(n)?
  11. How do I combine complex polygons?
  12. Smart design of a math parser?
  13. Are there any O(1/n) algorithms?
  14. What would cause an algorithm to have O(log log n) complexity?
  15. What is Constant Amortized Time?
  16. How to test randomness (case in point – Shuffling)
  17. Signed angle between two 3D vectors with same origin within the same plane
  18. How to calculate Tangent and Binormal?
  19. Plotting a point on the edge of a sphere
  20. Find point of intersection between two vectors in MATLAB
  21. What types of numbers are representable in binary floating-point?
  22. Finding the coordinates of points from distance matrix
  23. How does the CPU do subtraction?
  24. Handling errors in math functions
  25. How to calculate an RGB colour by specifying an alpha blending amount?
  26. Calculate angle between two Latitude/Longitude points
  27. Designing function f(f(n)) == -n
  28. Difference between some operators “|”, “^”, “&”, “&^”. Golang
  29. How are exponents calculated?
  30. Get direction (compass) with two longitude/latitude points

Leave a Comment