2,967 views

1 Answer

Best answer
3 votes
3 votes

Let us understand why we have only theta only and not "big theta" and "small theta".

Theta stands for tight bound so by "tight" we mean the function in terms of asymptotics is as much close as possible to the actual mathematical function as possible.Let us consider an example :

Let f(n) = 3n + 5    and   g(n)  = 2n

then here we can see that f(n)  =   θ(g(n)) as this 2 functions are linear but only differ in constants only(multiplication factor and addition factor).

Also according to the definition of Big - Oh , we have for any 2 +ve functions f(n) and g(n) , we have :

 f(n) <= c.g(n)   then we say  f(n)  =  O(g(n))  

According to the definition of Big - Omega , we have for any 2 +ve functions f(n) and g(n) , we have :

f(n)  >= c.g(n)   then we say  f(n)  =  Ω(g(n))  

So if we consider the equality condition of both of the above 2 conditions , we can merge them to have theta notation since f(n) = c.g(n) holds in both Big Oh and Big Omega notation at the same time.

However , now coming to your question :

Small - Oh is stricter in nature i.e. according to its definition ,

f(n)  < c.g(n)  then we say   f(n)  = o(g(n))   [f(n) is strictly less than g(n)]

Similar for Small - Omega notation as well ,

f(n)  > c.g(n)  then we say   f(n)  = ω(g(n))   [f(n) is strictly greater than g(n)]

So it is clearly evident that we cannot merge them since a function can not be strictly greater and strictly smaller at the same time , so there is nothing like Small - Theta notation. As an example ,

Let f(n)   =    n2              and              g(n)   =   n5

So f(n) is strictly less than g(n) but f(n) is not strictly greater than g(n) .So , only f(n) < g(n) inequality holds and not f(n) > g(n).

Thus we cannot merge them and so we do not have something like Small - Theta Notation.

Simply only Theta notation exists.

I hope I have addressed your doubt.

selected by

Related questions

3 votes
3 votes
0 answers
1
2 votes
2 votes
3 answers
2
shubhojit1412 asked May 25, 2019
2,206 views
If $T1(n) = \Theta(f(n))$&$T2(n) = \Theta(f(n))$Then, Is $T1(n) + T2(n) = O(f(n))$If yes, then how?
0 votes
0 votes
1 answer
3
2 votes
2 votes
1 answer
4