can you please help me to determine what is the time complexity of the following code:
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://mirror.codeforces.com/contest/1119/submission/52407323
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.
$$$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
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)$$$