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

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.

• Where did you come across this statement? – Juho Dec 2 '18 at 10:30
• $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) – chi Dec 2 '18 at 11:39
• Use the definitions. – Raphael Dec 2 '18 at 15:02
• It doesn't make sense to you because it is wrong. – gnasher729 Dec 2 '18 at 23:17

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. 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.