How to calculate big-theta
Solution 1
Big-theta notation represents the following rule:
For any two functions
f(n)
,g(n)
, iff(n)/g(n)
andg(n)/f(n)
are both bounded asn
grows to infinity, thenf = Θ(g)
andg = Θ(f)
. In that case,g
is both an upper bound and a lower bound on the growth off
.
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.
Navin Leon
Updated on May 30, 2020Comments
-
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 over 12 yearsHave you read e.g. en.wikipedia.org/wiki/Big_O_notation, which has a table comparing the various asymptotic notations?
-
Navin Leon over 12 yearsthanks 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 over 12 yearsHow 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 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 alsoT(n)>=n/2
, because at worst case you need to iterate the whole array, soT(n)>=Omega(n)
and therefore Theta(n) is asymptotic bound. -
Navin Leon over 12 yearsHow 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 over 12 years@Navin: Big-O, etc., are not about best or worst case.
-
Saeed Amiri over 12 yearsAs 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 over 12 yearsBoth definitions are equivalent, except for f = g = 0.
-
Ye. about 6 yearsFor the example algorithm above: Should min be initially negative infinity? And only be set if min < value ?