Oppgave 1
Det n2 som er det dominerende leddet.
Oppgave 2
Det minste heltallet k til høyre for 2 slik at ƒ1 ( n ) > ƒ2 ( n ) for alle verdier av n større enn k er lik 997. Vi har at ƒ1 ( 996 ) = 99201,60 og ƒ2 ( 996 ) = 99201,62.
Oppgave 3
Funksjonen ƒ( n ) = log2 (n2) kan skrives om, dvs. ƒ( n ) = log2 (n2) = 2 log2 n og siden log2 n allerede er i tabellen, tar vi ikke med den.
| Funksjonstype | n = 1 | n = 10 | n = 100 | n = 1.000 | n = 100.000 | |
| 1 | f ( n ) = 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | f ( n ) = log2 (log2 n) | − | 1,7 | 2,7 | 3,3 | 4,1 |
| 3 | f ( n ) = log2 n | 0 | 3,3 | 6,6 | 9,97 | 16,6 |
| 4 | f ( n ) = (log2 n)2 | 0 | 11,0 | 44,1 | 99,3 | 275,9 |
| 5 | f ( n ) = √n | 1 | 3,2 | 10 | 31,6 | 316,2 |
| 6 | f ( n ) = n | 1 | 10 | 100 | 1.000 | 100.000 |
| 7 | f ( n ) = n log2 n | 0 | 33,2 | 664,4 | 9.965,8 | 1.660.964,0 |
| 8 | f ( n ) = n3/2 | 1 | 31,6 | 1.000 | 31.622,8 | 31.622.776,6 |
| 9 | f ( n ) = n² | 1 | 100 | 10.000 | 1.000.000 | 10.000.000.000 |
| 10 | f ( n ) = n² log2 n | 0 | 100 | 10.000 | 1.000.000 | 166.096.404.744,4 |
| 11 | f ( n ) = n³ | 1 | 1.000 | 1.000.000 | 10 siffer | 16 siffer |
| 12 | f ( n ) = 2 n | 2 | 1.024 | 31 siffer | 302 siffer | 30103 siffer |
| 13 | f ( n ) = n! | 1 | 3.628.800 | 158 siffer | 2568 siffer | ∞ |
| Tabell - Asymptotisk rangering av funksjonstyper | ||||||
|---|---|---|---|---|---|---|