Asymptotic Growths of Functions

Question

How to determine if a given f(n) and g(n) is in theta, omega, big oh, little omega, or little oh? - I think one way of doing it is by plotting graphs of both functions f(n) and g(n). Even by plotting graphs how do we say when a f(n) is in theta, omega, big oh, little omega, or little oh? Am not clear on that. Can someone throw more details on that?

Also I am not sure if this is the correct way. Can anybody tell me if there is any other simpler way of doing this. Say example: f(n) = sq root(n) and g(n) = n^sin n

Answer 1

Here's how you compute Big-O given f(n) and g(n) using limits.

Plotting the functions for large values of x of both f(x) and g(x) on the same set of axes should help you immediately identify the asymptotic behavior.

Answer 2

First, you need to know the complexity of the function you're calling. This may be documented, but in the likely case that it is not you'll have to look at the source of those functions.

In the simple case you can count nested loops to get an idea of how long things take. If you have a loop from 1 to n inside a loop from 1 to t, and the only functions called inside take constant time (or you just do arithmetic operations inside, say), that's Theta(nt). If you happen to know that t <= n, it's also O(n²).

In more complicated cases you may need to use the Master Theorem or the like. In some cases it can be very hard (research-level) to determine the complexity!

Answer 3

You don't determine asymptotic growth by eyeballing it. There are formal definitions for each type of asymptotic growth relation that explain exactly and precisely what they mean. You determine whether two functions fit a given relation by determining mathematically if they satisfy the formal definition for the relation.

For example, one of several equivalent formal definitions for Big-O is as follows:

f = O(g) if and only if lim [ n -> inf ] ( f(n) / g(n) ) < inf

So, for example, if f(n) = n, and g(n) = n^2, you can observe that the limit as n -> infinity of n/n^2 = 0, and so f = O(g).

Or, if f(n) = n and g(n) = 2n, you can observe that as n-> inf, n / 2n -> 1/2 < inf, so again f = O(g).

However, if f(n) = n and g(n) = sqrt(n), you can observe that the limit as n -> infinity of n / sqrt(n) = infinity, so f != O(g).

Your example f and g is tricky to because sine oscillates between -1 and 1 as n increases. But Wolfram Alpha tells me that the limit in question is infinity, so sqrt(n) != O(n^(sin(n)).

Each other asymptotic growth relation has a similar formal definition that you can test to see if two functions satisfy it with respect to each other.

Edit:

It seems like you're looking for rules of thumb. Here's a quick and easy way to determine asymptotic order for relatively simple functions f and g. Consider the highest power of n in each function:

• If the highest power is the same, then f = O(g), g = O(f), f = Omega(g), g = Omega(f), f = Theta(g), g = Theta(f)
• If the highest power in f is smaller than the highest power in g, then f = O(g), f = o(g), g = Omega(f), g = omega(f)
• If the highest power in f is larger than the highest power in g, then f = Omega(g), f = omega(g), g = O(f), g = o(f)

Of course, if the functions are not polynomials in n, or are more complex and it's not easy to determine what the highest powers are (e.g. your example using sine), you will still have to revert back to the formal definition.

Some things that are always true:

• Theta is by definition the conjunction of O and Omega. f = O(g) ^ f = Omega(g) <=> f = Theta(g) [where ^ represents logical "and"]
• The "little" relations are stronger than the "big" relations. This means that f = o(g) => f = O(g) and f = omega(g) => f = Omega(g), but the reverse directions are not true.

Answer 4

Plotting a graph of the functions is theoretically not enough. (Although plotting a graph and then reasoning based on that might. Also, practically, it should be enough if you plot it for large enough values)

The correct way is to construct a proof:

The function f(n) is O(g(n)) iff there exist positive K and n0, such that f(n) < K × g(x) for every n > n0.

Let's assume this is true for f(n) = sqrt(n) and g(n) = n^sin n and some K and n0. Now consider a number n1 that

1. is bigger than this n0
2. is bigger than 1
3. is bigger than K²
4. for which the equation g(n1) = 1 holds

There is infinitely many numbers that satisfy those conditions: g(n1) = 1 when sin n1 = 0, that is n1 = a × π for any integer a. Limiting them to n1 > max(n0, 1, K²) still leaves infinitely many possibilities, so we pick one.

So we've got g(n1) = 1. What's the value of f(n1)? That's sqrt(n1), which is bigger than K (because n1 > K²).

Let's put it together: K < f(n1) < K × g(n1) = K, in other words K < K, which can't be true, that means the original assumption is wrong and so f(n) != O(g(n)).