-2
1) Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
2) Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
3) θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

What does this three equations suggests and how we could simplify this?

Nikunj Kakadiya
  • 2,689
  • 2
  • 20
  • 35
  • Looks like you messed up with the definitions of `Ο(f(n))` and `Ω(f(n))` – GAURANG VYAS Jun 16 '17 at 14:30
  • Do some research before asking a question - [What is the difference between Θ(n) and O(n)?](https://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on) If you're having trouble understanding the syntax in those equations, **which part** don't you understand, why are you posting 3 equations when 1 would do? – Bernhard Barker Jun 16 '17 at 14:30

1 Answers1

0

Those are definitions. So I would say they are already simplified. What you may want to do is translate them into natural language. In our case, plain English. Here it goes:

  1. We say that a function (or algorithm) is order f(n) if, from a certain point (say n = 100), this function is never greater than f(n).
    But there is a mistake in it. It should be g(n) ≤ c.f(n).
  2. I haven't seen it like that. Sorry.
  3. This notation implies that you are looking for a function (or algorithm) that is no greater than f(n) and also no smaller than g(n) from a certain n (say n = 200).

Those are useful when analyzing algorithm complexity. For the first, you want an upper bound for, usually, memory or time the algorithm consumes. For the second, a lower bound. And, for the third, both upper and lower bound.

Have you seen https://en.wikipedia.org/wiki/Analysis_of_algorithms?

Cheers!

DSchlingel
  • 15
  • 7