Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am learning algorithms, and I came across something very interesting.

The asymptotic bound of the linear equation (a * n)+b is O(n^2), for all a > 0.

This is same bound as a * n^2 + b * n + c, which is surprising.

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

It is important to realize, that O(f) represents a set of functions, for which c*f is an asymptotic upper bound for some constant c.

Just like there is more than one number that is bigger than 1, there is not just a single function that qualifies as an asymptotic upper bound for a function.

The tightest bound for (a*n) + b) is O(n), but it is also in O(n^2), but that's being very generous, and doesn't provide as much information as saying it's in O(n), because that is a much stronger statement.

I suggest you take a look at this similar question for more information.

share|improve this answer
add comment

Roughly speaking any two functions can be bounded by the same bound. The thing we really care is whether the bound is tight or loose. any constant O(1), linear and quadratic functions can be surely bounded by O(n2), or O(n3), or O(n4), or O(en).

But considering a very loose bound really can't give much information about a function itself. Thus, in practice, we should always choose the tightest bound for a function. So usually, when we talk about the bound, it could implicitly be the tightest bound.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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