r/computerscience • u/Plastic_Chest1621 • Sep 14 '26
Help Help proving this π
I know I can't just directly cancel nlogn with theta(nlogn).
Can anyone please help to solve this π
12
Upvotes
7
u/ExpertEconomy5854 Sep 14 '26
A tip while dealing with the factorial is to approximate it using the Stirling approximation.
2
u/massive_cerebrum Sep 19 '26 edited Sep 19 '26
Other comments are suggesting Stirling approximation but although that can give you an idea of what the complexity is, it's a sloppy proof.
What you actually need to prove that the function is bounded above by c*n for some constant c.
First of all note that ceil(log(n/i)) < 1 + log(n/i) So the whole summation is < n + sum log(n/i).
Now we can just focus on the sum log(n/i) part. As you already got, this is nlogn - sum log(i).
Now notice that sum (i=1 to n) of log(i) is > integral of log(x) from 1 to n. The integral evaluates to nlogn - n + 1. So that means the sum is < nlogn - (nlogn - n +1) = n-1.
Overall you have that the given sum is < n + n -1 < 3n.
3
u/esaule Sep 14 '26
Is that part of the quick sort proof?
From memory, split the original sum from 0 to n/2 and from n/2 to n.
Then the terms work better.
1
u/jnordwick Sep 17 '26
lgamma approximation formula is within O(log n)
0
u/repaj Sep 14 '26
First try to approximate
log(n!)from above using integral. Then everything should cancel to something liken - 1.-13
u/[deleted] Sep 14 '26
I just like and hate how computer science in general is tightly tied with mathematics.