LOGIKA I MATEMATYKA DYSKRETNA LISTA ZADA NR 5
1. Uporz¡dkuj list¦ ci¡gów ze wzgl¦du na asymptotyczne zachowanie dla du»ych n od najmniejszych do najwi¦kszych:
√
√
a) n 2 n log2 n n n n log2 n log2 n log n
2( n 5)
nn log2(log2 n) b) ( n!)2 ( n 2)!
n!
log2 n
√
√
c) 3 n 2 n
n! 2 n
n 2
2. Dla ka»dego z poni»szych ci¡gów znajd¹ najmniejsz¡ liczb¦ k tak¡, »e f( n) = O( nk).
a) f( n) = 13 n 2 + 4 n − 73
b) f( n) = ( n 2 + 1)(2 n 4 + 3 n − 8)
√
c) f( n) = n 2 − 1
3. Dla poni»szych ci¡gów wybierz takie a( n) z omawianych na wykªadzie przykªadów (P1-P6), »e f ( n) = O( a( n)), oraz a( n) jest mo»liwie najmniejsze.
a) f( n) = n 3 · log2 n p
b) f( n) = log2 n 4. Sprawd¹ prawdziwo±¢ poni»szych równo±ci.
a) 2 n+1 = O(2 n) b) ( n + 1)2 = O( n 2) c) 22 n = O(2 n) √
d) log73
2 n = O(
n)
e) (2 n)! = O( n!) Grzegorz Kondrat