1

I have the following code snippet and I want to know the time complexity of running it:

func fun(int n)
{
  var j = 1, i = 0;
  while (i < n)
  {
    // Some O(1) task
    i = i + log(j);
    j++;
  }
}

After some calculation, it comes up that the time complexity should be some kind of the form $c e^{W(n)} + ...=O(e^{W(n)})$, where $c$ is a constant and $W(n)$ is the product log function. I know the result in the above statement should be wrong but I don't know how to correct it.

Any correction and help would be appreciated.

shihpeng
  • 113

2 Answers2

2

This is actually quite simple. From the other answer it seems that you know that if $L$ is the number of iterations, then $n \sim L \log L$. We can safely take the log of both sides (you should think about why this is justified, especially because it is not true in reverse) to obtain $\log n \sim \log L + \log \log L$.

But since $\log \log L = o(\log L)$, the RHS is also asymptotic to $\log L$, i.e., $\log n \sim \log L$. (In other words, $\log n$ and $\log L$ are different, but not by much.)

Thus, $n \sim L \log L \sim L \log n$, which rearranges to $L \sim n/\log n$.

Erick Wong
  • 25,198
  • 3
  • 37
  • 91
1

Ok, I have done some approximated calculation for you. Let's see if it makes sense. First, you are trying to calculate sum of logarithms

$\sum_{j = 1}^{L} \log j \approx n$

Let us exponentiate both sides

$\prod_{j = 1}^{L} j = e^n$

Let's take the $L$-th square root

$\sqrt[L]{\prod_{j = 1}^{L} j} = e^{n/L}$

Now lets approximate geometric mean on the left hand side with the arithmetic mean

$e^{n/L} \approx \frac{\sum_{j=1}^L j}{L} = \frac{L(L+1)}{2L} = \frac{L+1}{2}$

Taking the logarithm again, we arrive at

$n \approx L(\log(L+1)-\log 2) \approx L \log L$

What you are actually interested in is $L(n)$, as that approximates your complexity. However, this function is not really invertible. What one can say is that since $n(L)$ is slightly super-linear, then $L(n)$ will be slightly sub-linear, meaning

complexity $< O(n)$

Edit: To be more precise,

$L \approx O(W(e^n))$

where $W(x)$ is the Lambert W-function, namely, the function defined by $x = W e^W$. There is a logarithmic expansion for it, but it is not very nice. See below

Lambert W function aproximation

I do not believe the problem can be answered perfectly. One can take any converging series for Lambert W-function, arbitrarily truncate the series and insert the terms into the $O()$ notation. However, I am not sure how much intuition it gives about actual behaviour. Analysing the implicit definition is not worse IMHO

Aleksejs Fomins
  • 2,240
  • Yes, L is the number of iterations the code takes, and indeed n≈L log(L). However, what I want to know is how to express L in the form of asymptotic notations (some thing like L = f(n) = O(e^n)), your final result seems to be a little vague. – shihpeng Apr 23 '18 at 08:31
  • 1
    @shihpeng If $n$ is asymptotic to $L \log L$, then $L$ is asymptotic to $n/\log n$. No need to bring in the $W$-function if all you want is the growth rate. – Erick Wong Apr 23 '18 at 10:11