asymptotic notations and their running time

Question

I know that for

$f(x) = O(g(x))$ running time $T(n) = O(n^3)$

$f(x) = \Omega(g(x))$ running time $T(n) = \Omega(n^2)$

but what is the $T(n)$ for $f(x) = Θ(g(x))$ ?

Also tell me running time for little-oh (o) & little-omega (\omega)

Also what is big-theta?

You can make the $\omega$ symbol by typing $\text{\omega}$. – MartianInvader Jul 01 '14 at 19:26 — MartianInvader, Jul 01 '14 at 19:26
To get $\omega$ you use \omega – Ross Millikan Jul 01 '14 at 19:26 — Ross Millikan, Jul 01 '14 at 19:26
The codes are $\Omega $ = \Omega and $\omega$ = \omega. – Ivo Terek Jul 01 '14 at 19:27 — Ivo Terek, Jul 01 '14 at 19:27
\omega is not working – Abhimanyu Aryan Jul 01 '14 at 19:33 — Abhimanyu Aryan, Jul 01 '14 at 19:33
@AbhimanyuAryan, put it between dollar signs like $\omega$ – Antonio Vargas Jul 01 '14 at 20:37 — Antonio Vargas, Jul 01 '14 at 20:37

score 0 · Accepted Answer · answered Jul 01 '14 at 19:05

0

$\Theta(g(n))$ means that that $\exists c_1, c_2$ such that $\forall n >N c_1 g(n) < f(n) <c_2 g(n)$. In other words, $f(n)$ is up to a constant both upper-and lower-bounded by $f(n)$. In your case (if I understand your question correctly) $f(x)$ is not $\Theta(g(x))$ because runtime bounds are of different order.

answered Jul 01 '14 at 19:05

Alex

19,262

Ok Got it @Alex – Abhimanyu Aryan Jul 01 '14 at 19:08

asymptotic notations and their running time

1 Answers1