daihan's blog

By daihan, 6 years ago, In English

can you please help me to determine what is the time complexity of the following code:

https://pastebin.com/s0QZhBBN

According to my calculation:

since multiset insert complexity is log(n) .

So in that code: each operation takes : i+log(i)

for i=1 takes 1+log(1) opearation

for i=2 takes 2+log(2) opearation

for i=3 takes 3+log(3) opearation
.

.

. for i=n takes n+log(n) opearation

now summing up all = ( log(1) + log(2) + log( 3 ) + .......+log(n) ) + ( 1+2+3+.....+n)

==> log( 1*2*3*.......*n) + (n*(n+1) /2 )

    ===> log( n! ) + (n*(n+1) /2 )

So Complexity: O( log(n! ) + n^2 ) . Am i right or wrong ?

my above code is a demo code . Original problem code :

https://codeforces.me/contest/1119/submission/52407323

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

You are technically right, but it is a well known fact that:

$$$O(log(n!)) = O(n\ log\ n)$$$

In such case your complexity becomes just $$$O(n\ log\ n\ +\ n^2)=O(n^2)$$$. If you are interested in why the first statement is true, you can look up Stirling's approximation.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    $$$log(n!) = \sum_{i=1}^{n} log(i) \le n \times log(n)$$$

    Since $$$log$$$ is a concave function, $$$n \times log(n/2) \le \sum_{i=1}^{n} log(i)$$$

    $$$O(n \text{ } log(n)) = O(log(n!))$$$

    **EDIT: ** THIS PROOF IS WRONG lol

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 3   Vote: I like it +16 Vote: I do not like it

      I think it is enough that $$$log(n!) = \sum_{i=1}^{n} log(i)$$$

      Then you can get the upper bound for complexity:

      $$$\sum_{i=1}^{n} log(i) \le \sum_{i=1}^{n} log(n)$$$

      $$$\sum_{i=1}^{n} log(i) \le n \times log(n)$$$

      Since we already have $$$O(... + \text{ } n^2)$$$ we don't care about lower bound of first part, it is already smaller than $$$O(n^2)$$$ and the overall complexity becomes $$$O(n^2)$$$

      No Stirling's approximation required

      P.S. I'm sorry, I didn't notice we are proving $$$O(log(n!)) = O(n \times log(n))$$$, not $$$O(log(n!) + n^2) = O(n^2)$$$