1.2-2 - Githubissues

walkccc / CLRS

📚 Solutions to Introduction to Algorithms Third Edition

https://walkccc.me/CLRS

MIT License

4.72k stars 1.26k forks source link

1.2-2 #404

Open mikelty opened 3 years ago

mikelty commented 3 years ago

wolfram says it's more like 2 to 26 though.

https://www.wolframalpha.com/input/?i=8n%5E2%3D64nlnn

jrmatos commented 3 years ago

I dont really know why they say it is 43, for real. I could get until n < 8logn. Can someone explain it please? Here is my math: problem

bozsudo commented 2 years ago

I dont really know why they say it is 43, for real. I could get until n < 8logn. Can someone explain it please? Here is my math:

Hi @jrmatos, did you ever figure out how to arrive at the solution given? Thanks.

Zaxxin-LLP commented 2 months ago

wolfram says it's more like 2 to 26 though.

https://www.wolframalpha.com/input/?i=8n%5E2%3D64nlnn

The input you gave is not lg, instead it is the natural logarithm. In the book, lg is equal to log₂ https://www.wolframalpha.com/input?i=8n%5E2%3D64n%28logn%2Flog2%29 approximately between 1.1 to 43.5. Since the the question doesn't specify a half input is valid, you round it down to the floor ( rounding it up causes 8n² to be greater than 64nlog₂n )

Zaxxin-LLP commented 2 months ago

I dont really know why they say it is 43, for real. I could get until n < 8logn. Can someone explain it please? Here is my math:

You'd have to use the Lambart W function (https://en.wikipedia.org/wiki/Lambert_W_function) I think.

This made me realise that I'm going into this far too early. I haven't even completed my IGCSE, and my algebra foundation isn't nearly the level that it is meant to be. Considering how this book is meant for students studying in college/uni, or those who have done mathematics to an extent, it likely assumes the reader already has some set level of ability in mathematics.