0
$\begingroup$

it's "gardening" time, which means studying algorithms. A question in Intro to Algorithms 3rd Edition is a chart asking me how many of N inputs can be placed into a function to get a certain amount of time.

lgN is the first function.

What are the max inputs of lgN to get 1 second? What is the max input of lgN to get 3 seconds? What is the max input of lgN to get 5 seconds?

[My attempt]

The first thing I did was acknowledge the amount of instructions per second my computer has, 4.0 gHZ means 4 billion instructions per second.

So, a log instruction can reasonably take 4 billion instructions, right? However, the more I thought about that the more it didn't seem right. . . An instruction isn't a function, and completing a fucntion can take more than a single instruction. Therefore, the idea that 4 billion instructions per second is 4 billion inputs for lg(N) was wrong.

So, I tried something different. Raw math. A computer with a 4gHZ computer does 4 billion instructions per second, right? So, all I have to do is get an input that makes lgN go over 4 billion or at least close to the mark. After all, if you entered a function like f(N*N) and that yielded about 4.127 billion in terms of time, you'd know that inputting that many inputs can measure up to about at least 1.127% of the time it took to complete an instruction, or a second.

So, inputting lg(4,000,000,000) as a start I end up with a raw 9.602.

The fact that I can have 4 billion inputs and have 9.602/4,000,000,000 is insane. . . That means my requirement for getting a second of time requires an astronomical number.

So, I decided to try something simpler, multiples of 2. I tried 2^4,000,000,000 and got infinity. Okay, getting warmer.

I tried 2^4000 and 2^1000. when I go far over 2^1000 I get infinity, for example.

lg(2^1023) = approximately 307. Whereas lg(2^1024) just goes straight to infinity.

So, I'm beginning to think that my process in trying to solve this problem is all wrong.

If any experienced algorithmic thinkers and or mathematicians can help me with this algorithm, I'd be extremely grateful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.