Can an algorithm be Theta but not Big-O or Omega?

[The111]

I'm not sure if there's a better sub-forum to put this question in.

I am new to computer science and programming in general, and I just recently learned about Big-O, Omega, and Theta, but I think I have a decent grasp on them (though I'd be happy to be proved wrong too). I understand that an algorithm can be Big O and Omega, but not Theta. For example if something is O(N) and Omega(1), then there is no Theta.

However, I ran into something recently where it is being claimed that a function is Theta(1), but is not Big O or Omega. Does this make any sense? Theta means there is are TWO constant factors to multiply by a certain function, ONE factor gives upper bound function and other ONE factor gives lower bound function. Right?

Big O means there is a constant factor to give upper bound (already established above as ONE of the TWO).

Omega means there is a constant factor to give lower bound (already established above as ONE of the TWO).

In essence it seems like we are saying that a thing is both A and B, but neither A nor B. Logically that doesn't make sense... if something is Theta it seems to me it has to be both Big O and Omega also (though the opposite is not true).

I welcome the thoughts of the more experienced in these matters. :popcorn:

[simeon87]

if something is Theta it seems to me it has to be both Big O and Omega also (though the opposite is not true).

That is also what I think.

[NovaAesa]

If f(n) is in Θ(1) then this implies it's also in Ο(1) and Ω(1).

[Barrucadu]

However, I ran into something recently where it is being claimed that a function is Theta(1), but is not Big O or Omega. Does this make any sense? Theta means there is are TWO constant factors to multiply by a certain function, ONE factor gives upper bound function and other ONE factor gives lower bound function. Right?

Let's start with some formal definitions of Big Oh and Big Omega:


f(n) ∈ O(g(n)) ⇔ ∃k > 0, n₀ ∀n > n₀ |f(n)| ⩽ |k×g(n)|
f(n) ∈ Ω(g(n)) ⇔ ∃k > 0, n₀ ∀n > n₀ |f(n)| ⩾ |k×g(n)|

So Big Oh can be thought of as "f grows no faster than g", and Big Omega can be thought of as "f grows no slower than g". Big Theta can be defined as follows:


f(n) ∈ Θ(g(n)) ⇔ ∃k₁ > 0, k₂ > 0, n₀ ∀n > n₀ |f(n)| ⩽ |k₁×g(n)| ∧ |f(n)| ⩾ |k₂×g(n)|

So Big Theta can be thought of as "f grows exactly as fast as g".

Now, hopefully it's not too difficult to see from those definitions that if f(n) ∈ Θ(g(n)) holds, then so do f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)). That is:


f(n) ∈ Θ(g(n)) ⇔ f(n) ∈ O(g(n)) ∧ f(n) ∈ Ω(g(n))

In summary, that claim is totally wrong, it's impossible for that to be the case. If you worked through the logic assuming that claim was correct, you would derive a contradiction.

[The111]

Let's start with some formal definitions of Big Oh and Big Omega:
Sadly, I am not too familiar with the formal definition or all the symbols involved. What course of study would I undertake to understand that math and those symbols? I'm guessing it's discrete math... I've actually started reading a big book on that but haven't got very far yet.

I have an aero engineering background and all the math that goes along with it, but am new to comp sci. I've only received a brief informal definition of the Big O concept in a data structures class I'm taking to jump into the comp sci world.

Thanks.


In summary, that claim is totally wrong, it's impossible for that to be the case.
The claim is coming from a college professor. :(

[simeon87]

The claim is coming from a college professor. :(

Is that really what the professor said? It sounds unlikely that he / she would make such a basic mistake. Despite all the formal symbols above, the intuitive concepts are quite obvious. Is it possible that you have interpreted a claim incorrectly? That's okay, it seems your understanding was right all along.

[The111]

Is that really what the professor said? It sounds unlikely that he / she would make such a basic mistake. Despite all the formal symbols above, the intuitive concepts are quite obvious. Is it possible that you have interpreted a claim incorrectly? That's okay, it seems your understanding was right all along.
On an exam it was asked that I give Big O, Theta, and Omega for a certain programming operation (flipping a specific single bit in a bitmap). My answer was:
O(1), Omega(1), and Theta(1)

The professor crossed off my O and Omega answers and said the correct answer was Theta only.

Not much room for interpretation there. I do not mean to throw this (anonymous) prof under the bus, but I did want to make sure my logic was sound before I discussed it further with him. Thanks for the input.

[schauerlich]

The professor crossed off my O and Omega answers and said the correct answer was Theta only.

Perhaps he thought that the Big-O and Big-Omega specifications were redundant?

[simeon87]

Perhaps he thought that the Big-O and Big-Omega specifications were redundant?

Could be. Theta(1) implies O(1) and Omega(1). In that case the question should have been phrased differently though as the question now asks for all three of them.

[Arndt]

Sadly, I am not too familiar with the formal definition or all the symbols involved. What course of study would I undertake to understand that math and those symbols? I'm guessing it's discrete math... I've actually started reading a big book on that but haven't got very far yet.



http://en.wikipedia.org/wiki/First-order_logic and
http://en.wikipedia.org/wiki/Set_theory cover the unknown symbols, I think.

There may be better elementary expositions, of course. Discrete mathematics uses sets a lot, and if theorems are proved, => and <=> will be in there too.

[The111]

Perhaps he thought that the Big-O and Big-Omega specifications were redundant?
His latest statement to me, in response to my argument as presented in the original post:

theta is approximately the same
thus no separate upper/lower bound

[slavik]

if you make a venn diagram, theta is the cross section.
big O is one circle, big omega is the other.
little o is the circle without theta, little omega same the other way

saying something is both big O and big omega doesn't make sense if it's theta, since theta is an intersection, not both.

[The111]

if you make a venn diagram, theta is the cross section.
big O is one circle, big omega is the other.
little o is the circle without theta, little omega same the other way

saying something is both big O and big omega doesn't make sense if it's theta, since theta is an intersection, not both.
How can you have an intersection of two circles, without two circles?

[NovaAesa]

His latest statement to me, in response to my argument as presented in the original post:

theta is approximately the same
thus no separate upper/lower bound

Your professor is wrong, simply put. There is a lower and upper bound, they are both constant bounds.