HiveBrain v1.2.0
Get Started
← Back to all entries
principleMajor

Time complexity $O(m+n)$ Vs $O(n)$

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
complexitytimestackoverflow

Problem

Consider this algorithm iterating over $2$ arrays $(A$ and $B)$

size of $ A = n$

size of $ B = m$

Please note that $m \leq n$

The algorithm is as follows

for every value in A:
    // code

for every value in B:
    // code


The time complexity of this algorithm is $O(n+m)$
But given that $m$ is strictly lesser than or equal to $n$, can this be considered as $O(n)$?

Solution

Yes:

$n+m \le n+n=2n$ which is $O(n)$, and thus $O(n+m)=O(n)$

For clarity, this is true only under the assumption that $m\le n$. Without this assumption, $O(n)$ and $O(n+m)$ are two different things - so it would be important to write $O(n+m)$ instead of $O(n)$.

Context

StackExchange Computer Science Q#139307, answer score: 39

Revisions (0)

No revisions yet.