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)$?
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)$.
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.
(expanding on my comment)
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.
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.
