CODEWITHSUNDEEP
time-complexity
Sumedh
Sumedh

Reputation: 404

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

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 ?

Upvotes: 0

Views: 1377

Answers (3)

RemcoGerlich
RemcoGerlich

Reputation: 31270

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".

Upvotes: 3

user2105505
user2105505

Reputation: 708

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

Upvotes: 2

Dr. Debasish Jana
Dr. Debasish Jana

Reputation: 7128

Yes, provided n is much larger than 1000

Upvotes: 1

Related Questions