3

I have been given the problem: 

f(n) are asymptotically positive functions. Prove f(n) = Θ(g(n)) iff g(n) = Θ(f(n)).

Everything I have found points to this statement being invalid. For example an answer I've come across states:

f(n) = O(g(n)) implies g(n) = O(f(n))
f(n) = O(g(n)) means g(n) grows faster than f(n). It cannot imply that f(n) grows
faster than g(n). Hence not true.

Another states:

 If f(n) = O(g(n)) then O(f(n)). This is false. If f(n) = 1 and g(n) = n 
 for all natural numbers n, then f(n) <= g(n) for all natural numbers n, so
 f(n) = O(g(n)). However, suppose g(n) = O(f(n)). Then there are natural
 numbers n0 and a constant c > 0 such that n=g(n) <= cf(n) = c for all n >= 
 n0 which is impossible.

I understand that there are slight differences between my exact question and the examples I have found, but I've only been able to come up with solutions that do not prove it. I am correct in thinking that it is not able to be proved or am I looking over some detail?

ROMANIA_engineer
  • 54,432
  • 29
  • 203
  • 199
user3068177
  • 357
  • 2
  • 5
  • 17
  • 5
    O is not the same as Theta. Look up the difference in their meanings – Ctx Jan 23 '16 at 22:00
  • 1
    Note that n = O(n), n = O(n^2), but n^2 != O(n) ... this simple example can help you to ignore some bad examples( like `f(n) = O(g(n)) implies g(n) = O(f(n))`, which can be true, but only for some particular situations ) – ROMANIA_engineer Jan 23 '16 at 22:00
  • 1
    `f(n) = O(g(n)) means g(n) grows faster than f(n)` - wrong. Roughly speaking, it means g grows *at least as fast* as f. – user2357112 Jan 23 '16 at 22:03
  • http://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on – user3068177 Jan 23 '16 at 22:11

1 Answers1

15

You can start from here:

Formal Definition: f(n) = Θ (g(n)) means there are positive constants c1, c2, and k, such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k.

Because you have that iff, you need to start from the left side and to prove the right side, and then start from the right side and prove the left side.

Left -> right

We consider that:

f(n) = Θ(g(n))

and we want to prove that 

g(n) = Θ(f(n))

So, we have some positive constants c1, c2 and k such that:

0 ≤ c1*g(n) ≤ f(n) ≤ c2*g(n), for all n ≥ k

The first relation between f and g is:

c1*g(n) ≤ f(n)     =>     g(n) ≤ 1/c1*f(n)    (1)

The second relation between f and g is:

f(n) ≤ c2*g(n)     =>     1/c2*f(n) ≤ g(n)    (2)

If we combine (1) and (2), we obtain:

1/c2*f(n) ≤ g(n) ≤ 1/c1*f(n)

If you consider c3 = 1/c2 and c4 = 1/c1, they exist and are positive (because the denominators are positive). And this is true for all n ≥ k (where k can be the same).

So, we have some positive constants c3, c4, k such that:

c3*f(n) ≤ g(n) ≤ c4*f(n), for all n ≥ k

which means that g(n) = Θ(f(n)).

Analogous for right -> left.

ROMANIA_engineer
  • 54,432
  • 29
  • 203
  • 199