Using the formal definition of asymptotic notations, prove that:

"The running time of an algorithm t$($n$)$ is $\backslash$Theta $($g$($n$))$ if and only if its worst$-$case running time t$\_($w$)($n$)$ is

O$($g$($n$))$ and its best$-$case running time t$\_($b$)($n$)$ is $\backslash$Omega $($g$($n$))"$

Notes:

There is no mention of the average case running time here:

t$($n$)$ is a function representing the running time of an algorithm in general, not for a specific

input class. It may have a different closed form for each input class, or no closed form at all.

t$\_($w$)($n$)$ is a function representing the running time of an algorithm for the specific class of

inputs designated as "worst case".

t$\_($b$)($n$)$ is a function representing the running time of an algorithm for the specific class of

inputs designated as "best case".

This is an $"$if and only if$"$ statement, so the proof usually involves two parts.