Adobe Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Comment hidden because of low score. Click to expand.
0
of 0 vote
It is log 1 + log 2 + ... + log n which is Theta(n log n).
A more precise value is given by Stirlings formula.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
We have sum of logarithms.
log 1 + log 2 + .... + log N
Using product rule from wiki page:
en.wikipedia.org/wiki/Logarithm
we have log (1*2*....*n) = log n!
According to Ramanujan formula from
en.wikipedia.org/wiki/Factorial
log n! = n * log n - n + ....
So, O(log n!) = O(n*log n)
Comment hidden because of low score. Click to expand.
0
of 0 votes
That's if you want to get all fancy up in here. I can show it's NlogN much more simply:
_
log 1 + log 2 + ... + log N < log N + ... +log N = NlogN (bound from above)
_
log 1 + log 2 + .. + log N > log N/2 + log (N/2+1) + ... + log N > (N/2) * log(N/2) = (N/2) (logN - log2) = O(NlogN) (bound from below)
Assuming j is an integer O(nlogn)
- NewCoderInTown April 19, 2012