complexity question

This sounds like a homework question... in fact, I know it is a homework problem. It is problem #50 in the Chapter 3 exercises in ''Discrete Mathematics, Fifth Edition'' by Richard Johnsonbaugh.

Despite this I will help you a little. Big-O notation is _very_ different than big-Theta notation. Big-O notation is an _upper bound_ (ie. if f(x) = 3x^2 + 5x then O(f(x)) = O(x^2) = O(x^3)) while big-Theta is the exact bound (ie. if f(x) = 3x^3 + 5x then big-theta(f(x)) = big-theta(x^2) != big-theta(x^3)). There is also big-omega which is lower bound (the opposite of big-O). Big-theta could also be thought of as the funciton where big-O = big-Omega for a function.

And, yes, there is a counterexample (many of them) for the equality you have listed. If you ask for more help I will give it but I will _not_ just give you a counterexample.

- mongrelprogrammer

quote:

---

Original post by mongrelprogrammer
This sounds like a homework question... in fact, I know it is a homework problem. It is problem #50 in the Chapter 3 exercises in ''Discrete Mathematics, Fifth Edition'' by Richard Johnsonbaugh.

---

hehe, good enough for me, thread terminated.


- Magmai Kai Holmlor

"Oh, like you''ve never written buggy code" - Lee

[Look for information | GDNet Start Here | GDNet Search Tool | GDNet FAQ | MSDN RTF[L] | SGI STL Docs | STFW | Asking Smart Questions ]

[Free C++ Libraries | Boost | ACE | Loki | MTL | Blitz++ | wxWindows| Spirit(xBNF)]
[Free C Libraries | zlib ]