CODEWITHSUNDEEP
algorithmtime-complexity
timeptr
timeptr

Reputation: 21

what is the time complexity of the algorithm?

It is a problem from an algorithm textbook, i think the time complexity is log(n!), but my classmate says it is nlog(n). Thanks very much for you reply!!

count ← 0
for i ← 1 to n do
    j ← ⌊n/2⌋
    while j ≥ 1 do
        count ← count + 1
        if j is odd then
           j←0
        else
           j ← j/2
        end if
    end while
 end for

Upvotes: 1

Views: 172

Answers (2)

Daniel Fischer
Daniel Fischer

Reputation: 183978

I think the time complexity is log(n!), but my classmate says it is nlog(n).

You're both right. As can be seen from Stirling's formula,

log n! = n * log n - n +O(log(n)),

(log is the natural logarithm here) more precisely:

log n! = (n + 1/2) * log n - n + 1/2 * log (2π) + O(1/n)

so O(log n!) and O(n*log n) are the same class.

Upvotes: 3

Déjà vu
Déjà vu

Reputation: 28850

Taking the worst case, n = 2p

  • loop 1 to n
  • for each loop, divide j by 2 until it is < 1

So, n * log2(n) iterations, or time complexity of O(n log(n))

--

(As per comment, the log base is not necessary in complexity, as log2(x) is actually log(x)/log(2) i.e. log(x) multiplied by constant)

Upvotes: 1

Related Questions