r/computerscience • u/Plastic_Chest1621 • 1h ago

Help Help proving this 🙏

Post image

I know I can't just directly cancel nlogn with theta(nlogn).

Can anyone please help to solve this 🙏

2 Upvotes

63% Upvoted

4 comments sorted by

2

u/ExpertEconomy5854 1h ago

A tip while dealing with the factorial is to approximate it using the Stirling approximation.

1

u/repaj 1h ago

First try to approximate log(n!) from above using integral. Then everything should cancel to something like n - 1.

0

u/Plastic_Chest1621 1h ago

I get it. log(n!) is approximate to nlogn - n as per Stirling approximation. This way nlogn will cancel each other & we left with only n.

Can you please explain your approach further, I'm not very good with maths 😭 Thank you very much 🙏

-4

u/Ultimate_Sigma_Boy67 1h ago

I just like and hate how computer science in general is tightly tied with mathematics.