What are sublinear algorithms?

Question

I was asked the following question from one of my teammates.

Which of the following expressions is not sublinear? O(log log n) O(n) O(logn) O(root(n)) 

I went through https://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time , but could not, but I'm not sure I fully understood it. Can someone point me in the right direction.

Answer 1

They say that the function f (x) grows faster than the other function g (x) if the limit of their relations when x approaches infinity goes to some positive bounded number, as can be seen from the definition below.

In the case of the sublinear, we want to prove that the function grows more slowly than c * n, where c is some positive number.

So, for every function f (n) in your list, the ratio of f (n) to (c * n) is required. If the limit is 0, this means that the function f (n) is sublinear. Otherwise, it grows at the same (approximate) speed n or faster.

 lim n->inf (log log n)/(c*n) = 0 (via l'Hopital's) 

(subline)

 lim n->inf (n)/(c*n) = 1/c != 0 

(linear)

 lim n->inf (log n)/(c*n) = 0 (via l'Hopital's) 

(subline)

 lim n->inf (sqrt(n))/(c*n) = 0 

(subline)

Answer 2

I think I understand why you are confused: on the wikipedia page you use, the Little-Oh designation is used:

Sublinear time

It is said that the algorithm works in sublinear time (often writing sublinear time) if T (n) = o (n)

Beware that T (n) = o (n) is a strong requirement than T (n) = O (n).

In particular, for a function from O (n) you cannot always have the inequality

 f(x) < kg(x) for all x > a 

is executed for every k that you choose. y=x and k=1 will prove that you are wrong, and the little-o-notation requires that every k satisfy this expression.

Any function O (n) is also not in o (n). So your non-sublinear expression is O (n).

I recommend reading this answer to continue your studies.