28

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.

station
  • 6,715
  • 14
  • 55
  • 89

2 Answers2

31

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)

erip
  • 16,374
  • 11
  • 66
  • 121
  • If a function grows sublinear, does this imply that sub-additivity holds, too? Or what constraints does the function have to fulfil in addition? I only found the properties for functions over a vector space. – Alex VII May 17 '18 at 09:08
  • @AlexVII I hesitate to claim this... but it's quite early and my coffee hasn't kicked in yet. :) – erip May 17 '18 at 12:01
  • @erip In the first definition, you mentioned the limit has to be positive bounded. Consider f(x) = x^2 and g(x) = x. f grows faster than g but \lim \limits_{x \to \infty} \frac{|f(x)|}{|g(x)|} = \infty is not bounded. – rims Dec 27 '19 at 02:32
  • @ironX that's true, good catch. The ratio doesn't necessarily need to be bounded to grow faster. Will edit. – erip Dec 27 '19 at 14:25
16

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

Community
  • 1
  • 1
Marco A.
  • 43,032
  • 26
  • 132
  • 246