-1

I refereed What is the difference between O(1) and Θ(1)? for the same. But I couldn't understand its mathematical difference.

R.s
  • 1
  • 3
  • 1
    This may be better suited for math.SE or cs.SE. Also, is the question really what you mean? O(1) and Θ(1) *are* the same, but that's generally not true of O(f(n)) and Θ(f(n)). – effeffe Apr 26 '18 at 09:09
  • templatetypedef gave an example where they aren't the same in the linked question. But if you're talking about algorithmic complexity, you're only interested in large values and not in fractional values like `1/n`. So O(1) and Θ(1) are practically the same in that case. – interjay Apr 26 '18 at 09:10
  • 2
    Possible duplicate of [What is the difference between O(1) and Θ(1)?](https://stackoverflow.com/questions/18677537/what-is-the-difference-between-o1-and-%ce%981) – interjay Apr 26 '18 at 09:18
  • (I should point out that my previous comment refers to the computational complexity area, where functions on natural numbers are used, not on reals) – effeffe Apr 26 '18 at 09:25

1 Answers1

1

f(x) = 1/x is O(1), but not Θ(1).

From CLRS book:

O(g(n)) = { f(n) : there exists positive constant c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0 }.

Θ(g(n)) = { f(n) : there exist positive constants c1, c2, and n0 such that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0 }.

Here g(n) is 1. And for 1/x you can't find positive c1 to satisfy c1 <= 1/x as x -> infinity.

Yola
  • 18,496
  • 11
  • 65
  • 106
  • `f(x)=x` is neither. – interjay Apr 26 '18 at 09:05
  • 1
    Though your answer is mathematically correct, I think it's worth pointing out that this is not true when we're talking about programming and computational complexity, where functions on natural numbers are used. In that domain, indeed, there is no difference. – effeffe Apr 26 '18 at 09:31
  • @effeffe in my example `x` could belong `N`, so the domain of `f` is `N` and the range is in `Q`. I can't find a proper wording to express that it is the same in computational complexity theory. Probably that would be appropriate to say that c.c. is never less than 1 as at least you need to call `return` statement. – Yola Apr 26 '18 at 09:53
  • Q is not in the natural numbers indeed. – effeffe Apr 26 '18 at 09:57
  • 1
    But yes, you're right, they're the same only under the assumption that the range of these functions ranges over positive natural numbers, my bad. – effeffe Apr 26 '18 at 10:20