1

Big theta which says it's both big o and big omega. As I understand big o is the upper bound that means for any large input the complexity should not exceed big o and the opposite for big omega. How is big theta both big o and big omega that means both big o and big omega will be the same line if I see it in a graph. Or in other words they both if we find the solution for a problem no matter how small or how big input we try the complexity will be same. Is that what it means?

wupiku
  • 85
  • 1
  • 5

1 Answers1

1

For two functions f(n) and g(n), you have the following meanings:

  • f(n) = O(g(n)) : This means that there exists some constant c>0 such that for big enough n, f(n) < c*g(n). Informally, "f doesn't grow faster than g".
  • f(n) = Ω(g(n)) : This means that there exists some constant c>0 such that for big enough n, f(n) > c*g(n). Informally, "f doesn't grow slower than g".
  • f(n) = Θ(g(n)) : This means that there exists some constants c_1>0 and c_2>0 such that for big enough n, c_1*g(n) < f(n) < c_2*g(n). Informally, "f grows about as fast as g".

So you see that Θ is indeed both O and Ω, because if f doesn't grow faster nor slower than g then it grows at the same speed (and conversely).

Tassle
  • 563
  • 3
  • 9
  • So, in other words, we write "f(n) = Θ(g(n))" only if "Ω(g(n)) = O(g(n))" applies? – resnet Sep 12 '19 at 04:35
  • 1
    Ah, that's the bad thing with this big-O notation and using an "=" symbol. The relation we are talking about here isn't really an equality (it's not an equivalence relationship) and what you wrote doesn't really make sense. f(n) = O(g(n)) would be better written as f(n) ∈ O(g(n)), then it would make more sense and prevent this kind of mistake. But you are partially right in the sense that f(n) ∈ Θ(g(n)) only if f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)). – Tassle Sep 12 '19 at 16:28
  • yeah, it felt definitely awkward to type that ... And your clarification is nice. Thanks! – resnet Sep 12 '19 at 18:34