algorithmasymptotic-complexitylimits

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.

Solution

  • 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 number (or infinity), as seen in the definition below.

    enter image description here

    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)