lg n = logarítmo na base 2
⌈ x ⌉ = teto de x = menor inteiro maior ou igual a x
⌊ x ⌋ = chão de x = maior inteiro menor ou igual a x
Para o 4, por exemplo, basta provar que existe c e N0, tal que:
lgn <= c* log10n, para todo n >= N0 ??
Aqui eu fiz que:
lg n <= log n/log 2 = lg n. Daí c= 1/log 2 e n0=1.
Está errado? Porque, segundo a página do Feofiloff, essa seria a ordem theta, não é?
OBS.: log n = logaritmo de n na base 10.
A abordagem do João parece correta.
c = 1/log 2 ~ 3,32
Utilizando c = 1 (< 3,32), como sugeriu o Gustavo, os valores de lg n ultrapassam os valores de log n.
Não está errado.
Theta é uma notação 'mais forte' que O.
lgn = Θ(logn) significa que lgn é limitada superiormente por algum c1*logn, p/ n >= n0; e limitada inferior para algum c2*logn. (c2 * logn <= lgn <= c1*logn)
lgn = Θ(logn) implica que lgn = O(logN)
Edit: Lendo melhor seu post, você mostrou que lgn é limitada superiormente por c*logn; isso é mostrar que que é O(logn)
Para mostrar que é theta, também teria que mostrar que é limitada inferiormente por algum c2 * logn...
Ah sim, li melhor e esqueci que ordem Theta(g) é basicamente Ômega(g) e O(g) simultaneamente. Valeu (: