20

If there are 2 algorthims that calculate the same result with different complexities, will O(log n) always be faster? If so please explain. BTW this is not an assignment question.

Varkolyn
  • 223
  • 1
  • 2
  • 4
  • 6
    It will always be faster for large enough *n*. – Phonon Feb 08 '12 at 20:56
  • [Difference between O(n) vs O(log n)](https://stackoverflow.com/questions/10369563/difference-between-on-and-ologn-which-is-better-and-what-exactly-is-olo) Hope this helps.. –  Feb 11 '19 at 17:17

3 Answers3

30

No. If one algorithm runs in N/100 and the other one in (log N)*100, then the second one will be slower for smaller input sizes. Asymptotic complexities are about the behavior of the running time as the input sizes go to infinity.

a3nm
  • 8,717
  • 6
  • 31
  • 39
  • so O(n) can be faster that O(log n) for extremely small input? – Varkolyn Feb 08 '12 at 21:02
  • 6
    1*n is O(n). 10000000000000000000000000000000*(log n) is O(log n). In such a case, O(n) will not just be faster on extremely small input. But as "n" grows toward infinity, *eventually* O(log n) will be faster. – Alex D Feb 08 '12 at 21:10
  • @Varkolyn: Not necessarily *extremely*. Depending on algorithm, the crosspoint can be very large in *n*! – kkm inactive - support strike Feb 08 '12 at 21:11
21

No, it will not always be faster. BUT, as the problem size grows larger and larger, eventually you will always reach a point where the O(log n) algorithm is faster than the O(n) one.

In real-world situations, usually the point where the O(log n) algorithm would overtake the O(n) algorithm would come very quickly. There is a big difference between O(log n) and O(n), just like there is a big difference between O(n) and O(n^2).

If you ever have the chance to read Programming Pearls by Jon Bentley, there is an awesome chapter in there where he pits a O(n) algorithm against a O(n^2) one, doing everything possible to give O(n^2) the advantage. (He codes the O(n^2) algorithm in C on an Alpha, and the O(n) algorithm in interpreted BASIC on an old Z80 or something, running at about 1MHz.) It is surprising how fast the O(n) algorithm overtakes the O(n^2) one.

Occasionally, though, you may find a very complex algorithm which has complexity just slightly better than a simpler one. In such a case, don't blindly choose the algorithm with a better big-O -- you may find that it is only faster on extremely large problems.

Alex D
  • 29,755
  • 7
  • 80
  • 126
0

For the input of size n, an algorithm of O(n) will perform steps proportional to n, while another algorithm of O(log(n)) will perform steps roughly log(n).

Clearly log(n) is smaller than n hence algorithm of complexity O(log(n)) is better. Since it will be much faster.

More Answers from stackoverflow