principleMajor
Time complexity $O(m+n)$ Vs $O(n)$
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
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)$?
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:
// codeThe 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)$.
$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.