3
$\begingroup$

How come O(n) + O(logn) = O(logn)?

When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is O(logn). It doesn't make sense to me since n is bigger than logn.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Where did you come across this statement? $\endgroup$
    – Juho
    Commented Dec 2, 2018 at 10:30
  • 4
    $\begingroup$ $O(n)+O(\log n)=O(n)$, not $O(\log n)$, as your intuition tells you. If you read $O(\log n)$ somewhere, that was a mistake. (Assuming you did not misread something, of course) $\endgroup$
    – chi
    Commented Dec 2, 2018 at 11:39
  • 1
    $\begingroup$ Use the definitions. $\endgroup$
    – Raphael
    Commented Dec 2, 2018 at 15:02
  • $\begingroup$ It doesn't make sense to you because it is wrong. $\endgroup$
    – gnasher729
    Commented Dec 2, 2018 at 23:17

1 Answer 1

Reset to default
2
$\begingroup$

As Chi say to you, if you have in a program two operations, one $\mathcal{O}(log{}n)$ and another $\mathcal{O}(n) $ you must take a superior bound, and your result will be $\mathcal{O}(n)$ in this case.

enter image description here

you can see here the complexity graph. If you say, that one operation take time $\mathcal{O}(n) $ , and nobody other operations take more of this, you can be at least $\mathcal{O}(n) $ time complexity. If just one operation are over $\mathcal{O}(n) $, the complexity will be change in new bound (and so on).

P.s Sum two bound, will maintain the most higher, multiply increse time complexity, like two neasted loop of $\mathcal{O}(n)$ will give you $\mathcal{O}(n^2)$ complexity.

I hope that this will help you.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Using plots to explain asymptotics is a bad idea. $\endgroup$
    – Raphael
    Commented Dec 2, 2018 at 15:03
  • 1
    $\begingroup$ Yes i got the point @Raphael but this example are very basic. This fuction all already know, and i hope the user know that O(n) is < than O(n^2). But for other example, the graph are very bad way to understand trend of the functions. Thanks for this suggestion. $\endgroup$
    – theantomc
    Commented Dec 2, 2018 at 15:40
  • $\begingroup$ Basic examples/exercises are designed to teach the right tools in a circumstance the learner can handle. It doesn't make much sense to use different tools that will fail in any non-trivial circumstance. $\endgroup$
    – Raphael
    Commented Dec 2, 2018 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.