WisFaq!

Big Oh

Hoi,

Ik ben een VWO-scholier maar ik houd me al een beetje bezig met universitair gerelateerde stof.

deze vraag:
Voor welke k geldt (log n)^k is O(n^1/_k)?
O staat hier voor orde.

Ik weet wat de definitie is van de order (big oh). Maar ik weet niet hoe ik kan aantonen voor welke k dit geldt.

F.
23-9-2010

Antwoord

Het geldt voor alle positieve k: om te beginnen moet je weten dat ln(n)/n naar nul convergeert voor n naar oneindig.
Als a positief is dan geldt ook dat ln(n)/n^a limiet nul heeft voor n naar oneindig (dat volgt omdat n^a ook naar oneindig gaat en dus ln(n^a)/n^a ook, maar de laatste uitdrukking is gelijk aan a·ln(n)/n^a.
Neem nu a gelijk aan 1/k²; dat volgt dus dat ln(n)/n^1/k2 limiet nul heeft; neem nu de k-de macht: (ln(n))^k/n^1/k heeft ook limiet nul.
Voor negatieve k geldt juist het omgekeerde n^1/k is kleine-o van (ln(n)^k).

kphart
27-9-2010