Difference between Big-Theta and Big O notation in simple language

by

Big O is giving only upper asymptotic bound, while big Theta is also giving a lower bound.

Everything that is Theta(f(n)) is also O(f(n)), but not the other way around.

T(n) is said to be Theta(f(n)), if it is both O(f(n)) and Omega(f(n))

For this reason big-Theta is more informative than big-O notation, so if we can say something is big-Theta, it’s usually preferred. However, it is harder to prove something is big Theta, than to prove it is big-O.

For example, merge sort is both O(n*log(n)) and Theta(n*log(n)), but it is also O(n2), since n2 is asymptotically “bigger” than it. However, it is NOT Theta(n2), Since the algorithm is NOT Omega(n2).

Omega(n) is asymptotic lower bound. If T(n) is Omega(f(n)), it means that from a certain n0, there is a constant C1 such that T(n) >= C1 * f(n). Whereas big-O says there is a constant C2 such that T(n) <= C2 * f(n)).

All three (Omega, O, Theta) give only asymptotic information (“for large input”):

  • Big O gives upper bound
  • Big Omega gives lower bound and
  • Big Theta gives both lower and upper bounds

Note that this notation is not related to the best, worst and average cases analysis of algorithms. Each one of these can be applied to each analysis.

More Related Contents:

  1. time complexity of recursion function
  2. What is a plain English explanation of “Big O” notation?
  3. What does O(log n) mean exactly?
  4. Constant Amortized Time
  5. What exactly does big Ө notation represent?
  6. Can hash tables really be O(1)?
  7. Is log(n!) = Θ(n·log(n))?
  8. Difference between Big-O and Little-O Notation
  9. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  10. Big-O for Eight Year Olds? [duplicate]
  11. Which algorithm is faster O(N) or O(2N)?
  12. Time complexity of Euclid’s Algorithm
  13. What would cause an algorithm to have O(log log n) complexity?
  14. What is pseudopolynomial time? How does it differ from polynomial time?
  15. Quick sort Worst case
  16. What is Constant Amortized Time?
  17. Computing set intersection in linear time?
  18. What would cause an algorithm to have O(log n) complexity?
  19. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  20. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  21. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  22. Quicksort superiority over Heap Sort
  23. Why do we ignore co-efficients in Big O notation?
  24. Big O when adding together different routines
  25. Time Complexity of two for loops [duplicate]
  26. Print the biggest K elements in a given heap in O(K*log(K))?
  27. Calculating phi(k) for 1
  28. The intersection of all combinations of n sets
  29. Prove that binary heap build max comparsion is (2N-2)
  30. Why is bubble sort O(n^2)?

Leave a Comment