Why are two O(N) methods regarded as O(N)?

Question

I have a method, in my program which calls two other methods that both have a linear time complexity. I don't know for sure if this would cause the method to have a time complexity if O(2N).

I know that constants drop off of time complexity which would make the method's time complexity O(N), but I am just not 100% sure. Can someone please elaborate on what a method like this would have for a time complexity and how?

read [this](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation?rq=1) — dumbPotato21, Mar 17 '17 at 17:45

score 1 · Answer 1 · answered Mar 17 '17 at 17:44

Think of it from this angle: if you eliminated the method calls and only had the code needed to run it in that method, what would its runtime be?

As you correctly deduce, you run two linear-time operations for a runtime of O(N) (since constants don't matter). This means that the overall method has a runtime complexity of O(N).

score 1 · Accepted Answer · answered Mar 17 '17 at 17:46

1

You are correct that the time complexity of thisMethod would be 2n. However, with big O notation, you do not include constants. Therefore, in big O notation, it would be O(n). Theta notation does include constants, so it would be theta(2n)

answered Mar 17 '17 at 17:46

beth

98
3
10

To continue from this: Big-O doesn't care about magnitude (coefficients) when it comes to complexity. Whether your function is O(N) or O(10N), it's still linear. – Jessie Mar 17 '17 at 21:34

Why are two O(N) methods regarded as O(N)?

2 Answers2