How to calculate big-theta

56,345

Solution 1

Big-theta notation represents the following rule:

For any two functions f(n), g(n), if f(n)/g(n) and g(n)/f(n) are both bounded as n grows to infinity, then f = Θ(g) and g = Θ(f). In that case, g is both an upper bound and a lower bound on the growth of f.

Here's an example algorithm:

def find-minimum(List) 
  min = +∞
  foreach value in List 
    min = value if min > value
  return min

We wish to evaluate the cost function c(n) where n is the size of the input list. This algorithm will perform one comparison for every item in the list, so c(n) = n.

c(n)/n = 1 which remains bounded as n goes to infinity, so c(n) grows no faster than n. This is what is meant by big-O notation c(n) = O(n). Conversely, n/C(n) = 1 also remains bounded, so c(n) grows no slower than n. Since it grows neither slower nor faster, it must grow at the same speed. This is what is meant by theta notation c(n) = Θ(n).

Note that c(n)/n² is also bounded, so c(n) = O(n²) as well — big-O notation is merely an upper bound on the complexity, so any O(n) function is also O(n²), O(n³)...

However, since n²/c(n) = n is not bounded, then c(n) ≠ Θ(n²). This is the interesting property of big-theta notation: it's both an upper bound and a lower bound on the complexity.

Solution 2

Big theta is a tight bound, for a function T(n): if: Omega(f(n))<=T(n)<=O(f(n)), then Theta(f(n)) is the tight bound for T(n).

In other words Theta(f(n)) 'describes' a function T(n), if both O [big O] and Omega, 'describe' the same T, with the same f.

for example, a quicksort [with correct median choices], always takes at most O(nlogn), at at least Omega(nlogn), so quicksort [with good median choices] is Theta(nlogn)

EDIT: added discussion in comments:
Searching an array is still Theta(n). the Theta function does not indicate worst/best case, but the behavior of the desired case. i.e, searching for an array, T(n)=number of ops for worst case. in here, obviously T(n)<=O(n), but also T(n)>=n/2, because at worst case you need to iterate the whole array, so T(n)>=Omega(n) and therefore Theta(n) is asymptotic bound.

Share:
56,345
Navin Leon
Author by

Navin Leon

Updated on May 30, 2020

Comments

  • Navin Leon
    Navin Leon almost 4 years

    Can some one provide me a real time example for how to calculate big theta.

    Is big theta some thing like average case, (min-max)/2?

    I mean (minimum time - big O)/2

    Please correct me if I am wrong, thanks

    • Oliver Charlesworth
      Oliver Charlesworth over 12 years
      Have you read e.g. en.wikipedia.org/wiki/Big_O_notation, which has a table comparing the various asymptotic notations?
    • Navin Leon
      Navin Leon over 12 years
      thanks for the link, yes i gone through this before; the table mainly describes abt big O and am hard to follow that, however i need real time example to get more understanding
  • Navin Leon
    Navin Leon over 12 years
    How about a searching a array of length n, here the best case is O(1) and worst case is O(n), then what is big theta in this case
  • amit
    amit over 12 years
    @Navin Leon: it is still Theta(n) worst case, the behavior of the Theta function is not worst/best case, it's asymptotic bound for the case you are looking for. i.e, searching for an array, T(n)=number of ops for worst case. in here, obviously T(n)<=O(n), but also T(n)>=n/2, because at worst case you need to iterate the whole array, so T(n)>=Omega(n) and therefore Theta(n) is asymptotic bound.
  • Navin Leon
    Navin Leon over 12 years
    How about a searching a array of length n, here the best case is O(1) and worst case is O(n), then what is big theta in this case
  • Oliver Charlesworth
    Oliver Charlesworth over 12 years
    @Navin: Big-O, etc., are not about best or worst case.
  • Saeed Amiri
    Saeed Amiri over 12 years
    As I know that's not a big theta definition, there isn't anything says F(n)/G(n) it just says f(n) <= C1 g(n) and g(n) <= C2 f(n) ...., for your definition counter example, assume f = g = 0 for all n, so your definition has no meaning for this sample.
  • Victor Nicollet
    Victor Nicollet over 12 years
    Both definitions are equivalent, except for f = g = 0.
  • Ye.
    Ye. about 6 years
    For the example algorithm above: Should min be initially negative infinity? And only be set if min < value ?