Notação Theta:

 - Considere uma função T definida nos inteiros positivos
 
 - T(n) = Theta(f(n))
    - significa que, para um n suficientemente grande, f(n) limita T(n) tanto inferiormente quanto superiormente

 - Exemplo usando um gráfico
 
 - Definição formal:
 
    - T(n) = Theta(f(n)) se existem constantes n_0, c1 > 0 e c2 > 0 tais que c1 * f(n) <= T(n) <= c2 * f(n) para todo n >= n_0
	
	   - note que n_0, c1 e c2 não podem depender de n



Exemplo 1:

 - T(n) = (1/2)n^2 + 3n
 
    - T(n) é O(n)?
 
    - T(n) é Omega(n)?
 
    - T(n) é O(n^3)?
 
    - T(n) é Theta(n^2)?



Exemplo 2:

 - T(n) = max{f, g} é Theta(f(n) + g(n))
 
Prova: 
 - Queremos encontrar constantes c1, c2 e n_0 tais que, para todo n >= n_0, temos c1 * (f(n) + g(n)) <= T(n) <= c2 * (f(n) + g(n))
 
T(n) = max{f(n), g(n)}
     <= f(n) + g(n)

 - Portanto, para c2 = 1 e n_0 = 1 temos T(n) <= c2 * (f(n) + g(n))

Como f(n) + g(n) = max{f(n), g(n)} + min{f(n), g(n)} <= 2 * max{f(n), g(n)}

T(n) = max{f(n), g(n)}
     >= (f(n) + g(n))/2

 - Portanto, para c1 = 1/2 e n_0 = 1 temos T(n) >= c1 * (f(n) + g(n))



Exemplo 3:

 - T(n) = 2^n + 15n^2 é Theta(2^n)?
 
Prova:
 - Queremos encontrar constantes c1, c2 e n_0 tais que, para todo n >= n_0, temos c1 * 2^n <= T(n) <= c2 * 2^n
 
T(n) = 2^n + 15n^2
	 >= 2^n

 - Portanto, para c1 = 1 e n_0 = 1 temos c1 * 2^n <= T(n)

T(n) = 2^n + 15n^2
     <= 2^n + 2^n 		(para n >= ?16?		2^n >= 15n^2 --> n >= lg 15n^2 --> n >= lg 15 + 2 lg n --> n - 2 lg n >= lg 15)
	 = 2 * 2^n

 - Portanto, para c2 = 2 e n_0 = 16 temos T(n) <= c2 * 2^n

 - Note que, quando estamos demonstrando que uma função é Theta de outra, podemos chegar a n_0 diferentes para os limitantes inferior e superior. No final usamos o maior dentre eles.