> > What is the complexity of the following code (how fast does it run)?
> >
> > for (int i=n; i > 0; i = i--)
> > for (int j=1; j < i; j = j*2)
> > print(j);
> >
>
> Leaving aside typos and rules, is it
>
> n * (log(n-l) + 1) / 2
>
> or O(n log n) while l is small compared to n, and approaching
> O(n) as l
> approaches n???
If we have
for (int i=n; i > 0; i--)
for (int j=1; j < i; j = j*2)
print(j);
Then we get
i j # prints
----------------------------------------------------------------
n 1, 2, 4, ...2^k k+1 = O(log n)
(k+1 terms, 2^k <= n)
n-1 1, 2, ... 2^k <= n-1 k+1 = O(log n-1) = O(log n)
n-2 1, 2, ... 2^k <= n-2 k+1 = O(log n-2) = O(log n)
...
2 1 1 = O(log 2) = O(log n)
1 - 0 = O(log n)
The outer loop runs n times, and the inner loop always runs in log n steps
or less,
in other words in O(log n), so the total running time is n*O(log n) =
O(n*log n).
If you analyze it more precisely, then the running time (number of times
that the
print statement is executed) is:
T(n) = log(n) + log(n-1) + log(n-2) + ... + log(3) + log(2) + log(1)
(where log is logarithm in base 2)
and so -- because log a + log b = log(a*b) --
T(n) = log(n!) = O(n*log n)
