18
$\begingroup$

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

size of A = n

size of B = m

Please note that m <= 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)?

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Apr 25 at 20:07
37
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Apr 25 at 20:09
11
$\begingroup$

Yes, since $n + m \leq 2n$ the algorithm is $O(n)$. However, you may wish to write $O(m + n)$ because it clearly shows which variables the algorithm depends on, and what each variable does to the complexity.

$\endgroup$
0
0
$\begingroup$

(expanding on my comment)

Technically No

You need to be very careful here, as there is a difference between algorithmic time complexity and runtime. In the case you have described, the runtime may be O(n) but the algorithm itself is O(n+m).

This is because, without your external constraints, the algorithm's time complexity cannot be determined without knowing both m and n.

If you wanted to make the algorithm itself O(n), you would need to explicitly encode your external constraint that m<n within the algorithm itself. Adding a check that aborts if m>n would work.

Unless...

The above does not hold if m < n by definition (ie it arises from a fundamental property of your data structures).

Say, for example, A is an array and B is an array composed of only the elements at the even indices of A. Then m is indeed < n by definition, and no check is required.

In cases like these the answer is yes, the algorithm is O(n). In fact, it would be 'incorrect' (assuming you are going for a tight upper bound) to say it is O(n+m) since the asymptotic performance depends entirely on n.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Apr 25 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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