What are sublinear algorithms?
I have been asked the following question by one of my fellow mates.
Which of the following expressions is not sublinear?
O(log log n)
O(n)
O(logn)
O(root(n))
I have gone through https://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time but couldn't but I am not sure that I have understood it completely. Could someone point me in the right direction.
A function, f(x), is said to grow faster than another function, g(x), if the limit of their ratios as x approaches infinity goes to some positive, bounded number, as seen in the definition below.
In the case of sublinear, we want to prove that a function grows slower than c*n, where c is some positive number.
Thus, for each function, f(n), in your list, we want the ratio of f(n) to (c*n). If the limit is 0, this means the function, f(n), is sublinear. Otherwise it grows at the same (approximate) speed of n or faster.
lim n->inf (log log n)/(c*n) = 0 (via l'Hopital's)
(sublinear)
lim n->inf (n)/(c*n) = 1/c != 0
(linear)
lim n->inf (log n)/(c*n) = 0 (via l'Hopital's)
(sublinear)
lim n->inf (sqrt(n))/(c*n) = 0
(sublinear)
I think I understood why you're confused: the wikipedia page you link uses Little-Oh notation:
Sub-linear time
An algorithm is said to run in sub-linear time (often spelled sublinear time) if T(n) = o(n)
Beware that T(n) = o(n) is a stronger requirement than saying T(n) = O(n).
In particular for a function in O(n) you can't always have the inequality
f(x) < k g(x) for all x > a
satisfied for every k
you choose. y=x
and k=1
will prove you wrong and little-oh notation requires every k
to satisfy that expression.
Any O(n) function is not also in o(n). Thus your non-sublinear expression is O(n).
I recommend reading this answer to continue your studies
链接地址: http://www.djcxy.com/p/39886.html上一篇: o符号示例
下一篇: 什么是次线性算法?