What is the tight bound for big O? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

When referring to big o, what is considered the tight bound?

For example, in the function, f(n) = 10c₇n^3 + 10c₄nlog(n)) // This function represents the number of operations in terms of n //

according to this example, the tight bound for big O would be O(n³).

In this example, why is n³ considered the tight bound for Big O? What characteristics does a tight bound exhibit?

Also, what is a tilde value?

according to this example, the tilde value for this function would be 10c₇n³.

I have searched online, but I can't seem to find anything useful. I was hoping someone could clear this up.

Answer 1

The tight bound is that term which best captures the overall growth characteristics of your function as you increase the value of n.

In other words, 10c7n^3 + 10c4nlog(n)) is O(n^3) because the term with n^3 in it has the greatest effect on the computing time of the function, as n increases. All of the other terms in the function have an insignificant effect over the amount of computing time, compared to the cubed term.

What you call the tilde value appears to be merely the term containing the tilde; i.e. the term containing the highest power of n. (the "terms" are those parts of the function separated by a + or - sign)

Answer 2

The term tight bound says that both f(n)/n^3 and n^3/f(n) are bounded. f(n)~10*c7*n^3 says that f(n)/10*c7*n^3 rends to 1 as n tens to infinity.