15
$\begingroup$

I can't imagine one that is not polylogarithmic but logarithmic.

$O(\log N)$ satisfies both.

What about $O(\log^{3}N)$, $O(\log^{100}N)$, and $O(\log^{10000}N)$ ?

Let's say $N=10^{10}$

$\endgroup$
7
  • 1
    $\begingroup$ What's the context of this? I'm not sure this difference matters a lot in cryptography. $\endgroup$
    – Elias
    Jun 26 '17 at 13:43
  • 1
    $\begingroup$ I saw one paper a few years ago with Goldwasser that had a polylog function, so understanding the definition would make sense. But it would be nice if OP gave some crypto context, yes. $\endgroup$
    – user47922
    Jun 26 '17 at 13:50
  • $\begingroup$ Here's what I was remembering $\endgroup$
    – user47922
    Jun 26 '17 at 13:51
  • $\begingroup$ What is one in your question? A problem? Also, if you fix $N=10^{10}$ they are all O(1) :) $\endgroup$ Jun 26 '17 at 16:53
  • 1
    $\begingroup$ I should have mentioned the utility of this topic. Since papers from crypto community explicitly use the terms $\mathsf{polylogarithmic}$ and $\mathsf{logarithmic}$, not interchangeably. $\endgroup$
    – mallea
    Jun 28 '17 at 2:21
20
$\begingroup$

Definitions:

An algorithm is said to run in

  • logarithmic time if $T(n) = O(log(n))$
  • polylogarithmic time if $T(n) = O(log(n)^k)$ (also written as $T(n) = O(log^k(n))$)

That means they are the same for $k=1$. Otherwise they are different and your other examples are all polylogarithmic. I'm not sure how exactly to explain what the difference is but maybe a picture will help you:

log(x) and log^3(x)

$\endgroup$
3
  • $\begingroup$ What does π‘™π‘œπ‘”^π‘˜(𝑛) approach as n goes to infinity? Does it approach a line n? $\endgroup$ Sep 16 at 18:32
  • $\begingroup$ Some quick plotting in python shows that it seems to grow very fast initially, but at some point, will still grow slower than n. Basically approaches: ___ | as opposed to / / If this is wrong, please let me know. $\endgroup$ Sep 16 at 18:40
  • $\begingroup$ Ah comments don't show newlines, so my simple ascii plot didn't format. Basically a corner that goes vertically up then horizontal (when very zoomed out compared to the diagonal line n) $\endgroup$ Sep 16 at 18:42
6
$\begingroup$

An algorithm is said to take logarithmic time if T(n) = O(log n).

An algorithm is said to run in polylogarithmic time if T(n) = O((log n)^k), for some constant k.

Wikipedia: Time complexity

Logarithmic time

An algorithm is said to take logarithmic time if $T(n) = O(\log n)$. Due to the use of the binary numeral system by computers, the logarithm is frequently base 2 (that is, $\log_2 n$, sometimes written $\lg n$). However, by the change of base for logarithms, $\log_a n$ and $\log_b n$ differ only by a constant multiplier, which in big-$O$ notation is discarded; thus $O(\log n)$ is the standard notation for logarithmic time algorithms regardless of the base of the logarithm.

Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.

An $O(\log n)$ algorithm is considered highly efficient, as the operations per instance required to complete decrease with each instance.

A very simple example of this type is an algorithm that cuts a string in half, then cuts the right half in half, and so on. It will take $O(\log n)$ time ($n$ being the length of the string) since we chop the string in half before each print (we make the assumption that console.log and str.substring run in constant time). This means, in order to increase the number of prints, we have to double the length of the string.

Polylogarithmic time

An algorithm is said to run in polylogarithmic time if $T(n) = O((\log n)^k)$, for some constant $k$. For example, matrix chain ordering can be solved in polylogarithmic time on a Parallel Random Access Machine.

$\endgroup$
3
  • $\begingroup$ thanks for your quick response! Is there any borderline b/w them? $\endgroup$
    – mallea
    Jun 26 '17 at 12:24
  • $\begingroup$ @zorutic - for O((log n)^k), when k=1 than it is Logarithmic time $\endgroup$
    – Yaron
    Jun 26 '17 at 12:28
  • $\begingroup$ Your polylogarithmic time expression is missing a ^. ​ ​ $\endgroup$
    – user991
    Jun 26 '17 at 19:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.