o-notation?

Question

whats the meaning of "tight" here? it means "restricted" or "fixed"? (in math)

We use o-notation to denote an upper bound that is not asymptotically tight.

Answer 1

I'm not sure we're talking about the same thing, but:

In Computer Science, O-notation (pronounced "Big-Oh") is used to "bound from above" the running time of an algorithm.

The formal definition of it is:

f(x) is O(g(x)) if there exist constants C and k such that

|f(x)| <= C|g(x)|

whenever x > k.

It's usually used to find the tightest bound possible, but the definition allows you to use less tight bounds.

For instance, f(x) = x^2 + 2x + 7 is O(x^2), but it's also O(x^3), O(x!), etc.

For a "tight bound" from above AND below there's Big-Omega, but people usually care more about the worst case, so Big-O is the standard.

Answer 2

The answer is yes to both. The big 'O' means 'on the order of' and simply expresses that (in the first case) the function roughly increases by a factor of 4 if n is doubled while the function in the 2'nd case increases linearly with increasing n. HTH, Doug

Answer 3

In analysis, a function is said to be o(x) if o(x)/x --> 0 as x-->0.
In this case, it is necessary that o(x)-->0, so it means that o(x) functions tend to zero "so fast" that even if you divide them by x and let x-->0, they still go to zero. For example, x^2 is o(x) but x is not, even though it goes to zero. Among other fields, this notation is commonly used in probability theory.

Answer 4

I'm sorry, that sounds like one of those obscure, and nebulous engineering terms.

Those folks come up with the darndest things. It's not among anything familiar in the typical science realm that I'm familiar with.

So, I'm guessing that it has to do with a limit to some value....loose, not as near as it woudl be as if it were actually an asymptote.

Answer 5

This will not help you as it is probably more complicated than what your text book has. However, it may put fizixx on the right track.