关于时间复杂度O(2m+n)与O(kn)的正确性验证问询

Hey there! Let's walk through your two time complexity questions clearly, with the core rules of big O notation in mind.

Absolutely, this is 100% correct!

Big O notation is all about describing the asymptotic growth rate of an algorithm—we don’t fixate on constant coefficients because they don’t change how the runtime scales as input sizes grow extremely large.

In your code, you’ve got two loops over the m-sized array (totaling 2m operations) plus one loop over the n-sized array (n operations). Since 2m grows at the exact same rate as m (doubling the constant doesn’t make the growth faster or slower as m approaches infinity), we can safely drop the constant 2. That leaves us with O(m + n), which is the proper way to express this algorithm’s time complexity.

It depends entirely on what k represents!

Big O notation hinges on whether k is a constant or a variable tied to input size:

• If k is a fixed constant (meaning it never changes, no matter how big n gets—like k=4, set by an input that’s totally independent of n), we can treat k as a constant factor and drop it. So the time complexity simplifies to O(n), not O(kn).
• If k is a value calculated based on the input size n (like k=n, k=log n, or k=sqrt(n)), then k is part of the asymptotic growth rate. In this case, the time complexity is indeed O(kn), because k scales with n and directly impacts how the runtime grows.

For quick examples:

• If k is always 5, no matter what n is: looping 5 times over n elements is just 5n operations, which is O(n).
• If k equals n (so you loop n times over n elements): that’s n² operations, which is O(n²) = O(kn) when k=n.

内容的提问来源于stack exchange，提问作者atatatatatat