There are many hierarchy theorems based on Time, Space, Nondeterminism, Randomization etc. Time Hierarchy Theorem (Version 1) : If f,g are time-constructible functions satisfying f(n)logf(n)=o(g(n)), then DTIME(f(n))⊊ Proof: Consider the following Turing machine D: "On input x, run for f(|x|)\log (f(|x|)) steps the Universal TM \mathcal{U} to simulate the execution of M_x on x. If \mathcal{U} outputs some bit b \in\{0,1\} in this time, then output the opposite answer (i.e., output 1-b ). Else output 0.” Here M_x is the machine represented by the string x. By definition, D halts within f(n)\log (f(n)) steps and hence the language L decided by D is in DTIME(g(n)). Claim: L \notin DTIME (f(n)) Proof: For contradiction's sake, assume that there is some TM M and constant c such that TM M, given any input x \in\{0,1\}^*, halts within cf(|x|) steps and outputs D(x)....
Theorem : If all zeros of a polynomial P(z) lie in a half-plane, then all zeros pf the derivative P'(z) lie in the same half-plane. Proof: Let P(z) be any polynomial with degree n. Then P(z)=a(z-a_1)(z-a_2)\cdots(z-a_n) where a_1,a_2,\dots,a_n are the zeros of P(z). Hence \frac{P'(z)}{P(z)}=\frac1{z-a_1}+\frac1{z-a_2}+\cdots+\frac1{z-a_n}Suppose the half plane H defined as the part of the plane where IM\frac{z-a}{b}<0. Suppose z If a_k is in H and z is no, we have then Im\frac{z-a_k}{b}=Im\frac{z-a}{b}-Im\frac{a_k-a}{b}>0But the imaginary parts of reciprocal numbers have opposite signs. Therefore, under the same assumption, Im\ b(z-a_k)^{-1}<0.Now this is true for all k we conclude that Im\frac{bP'(z)}{P(z)}=\sum_{k=1}^{n} Im\frac{b}{z-a_k}<0 and consequently P'(z)\neq 0. Hence z is not a root of P'(z) concluding that all roots of P'(z) lie in H. \blacksquare