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}$
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ What's the context of this? I'm not sure this difference matters a lot in cryptography. $\endgroup$– EliasJun 26, 2017 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$– user47922Jun 26, 2017 at 13:50
-
$\begingroup$ Here's what I was remembering $\endgroup$– user47922Jun 26, 2017 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$– Alessandro CosentinoJun 26, 2017 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$– malleaJun 28, 2017 at 2:21
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
3
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:
-
$\begingroup$ What does 𝑙𝑜𝑔^𝑘(𝑛) approach as n goes to infinity? Does it approach a line n? $\endgroup$ Sep 16, 2021 at 18:32
-
1$\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, 2021 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, 2021 at 18:42
$\begingroup$
$\endgroup$
3
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.
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.
-
$\begingroup$ thanks for your quick response! Is there any borderline b/w them? $\endgroup$– malleaJun 26, 2017 at 12:24
-
$\begingroup$ @zorutic - for O((log n)^k), when k=1 than it is Logarithmic time $\endgroup$– YaronJun 26, 2017 at 12:28
-
$\begingroup$ Your polylogarithmic time expression is missing a
^. $\endgroup$– user991Jun 26, 2017 at 19:10