Example: log(n)
ë
O(n
1/2
).
l
This holds provided 1/n
ë
O(n
-1/2
),
according to the derivative rule.
l
Apply the limit rule:
lim ((1/n) / n
-1/2
)
= lim (1/ n
1/2
)
= 0
l
This bound is not tight, since the limit is 0.
l
Therefore n
-1/2
ì
O(1/n).