\require{AMSmath}
WisFaq - de digitale vraagbaak voor wiskunde en wiskunde onderwijs


Printen

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(n1/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.
Leerling bovenbouw havo-vwo - donderdag 23 september 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)/na limiet nul heeft voor n naar oneindig (dat volgt omdat na ook naar oneindig gaat en dus ln(na)/na ook, maar de laatste uitdrukking is gelijk aan a·ln(n)/na.
Neem nu a gelijk aan 1/k2; dat volgt dus dat ln(n)/n1/k2 limiet nul heeft; neem nu de k-de macht: (ln(n))k/n1/k heeft ook limiet nul.
Voor negatieve k geldt juist het omgekeerde n1/k is kleine-o van (ln(n)k).

kphart
maandag 27 september 2010

©2001-2024 WisFaq