Is O(1000n) = O(n) when n>>1000

Question

If it is explicitly given that n>>1000, can O(1000n) be considered as O(n) ?? In other words, if we are to solve a problem(which also states that n>>1000) in O(n) & my solution's complexity is O(1000n), is my solution acceptable ?

Answer 1

If the function is O(1000n), then it is automatically also O(n).

After all, if f(n) is O(1000n), then there exists a constant M and and an n0 such that

f(n) <= M*1000n

for all n > n0. But if that is true, then we can take N = 1000*M and

f(n) <= N*n

for all n > n0. Therefore, f is O(n) as well.

Constant factors "drop out" in big-O notation. See Wikipedia, under "multiplication by a constant".

Answer 2

Your solution is in polynomial time, so any constants won't matter when n is arbitrarily large. So yes, your solution is acceptable.

Answer 3

Yes, provided n is much larger than 1000