Algoritmi ajaline keerukus
Eksponentsiaalne keerukus f ( n ) O( a n ) a>1. s.t. f(n)<= c* a n
Ül 408. Näidata, et n + n log 2 n O( log 2 n )
n
Kuna nlim = 0 , siis n< n log 2 n kui n>N
n log n
2
n + n log 2 n < n log 2 n + n log 2 n = 2 * n log 2 n
seetõttu valime c=2 ja n>N
409.
a) Näidata , et n! = O( n n )
seega peame näitama n!<=c* nn
n!=1*2*3*...*nindukstiooniga
n=0 siis 0<=c*20 ehk 0 korral on täidetud
eeldame et kehtin n=k korral: st. k<=c*2k
tõestame et kehtib n=k+1 korral: k+1<=c*2k+1=c*2k *2 = c*2k+ c*2k
k+1
annaabi.ee 
