Solving computer program running times

Question

I have a question and im not sure how to tackle it.... algorithms have running times proportional to the following functions of the input size, denoted N

Log to the base 2 of (N)

In one minute of computing time, they can each successfully complete processing an input of size 1000. What size input can each successfully handle given one hour of computing time?

Answer 1

In a problem like this, you can treat a time complexity formula O(nlog₂(n)) like an approximate formula for how long the program will take to run, where O is a constant that depends on the program.

So writing out the given information:

O*1000*log₂(1000)=1

And the unknown:

O*x*log₂(x)=60

We can cross multiply to eliminate O and get one equation with x on the left. Log₂ on both sides can be replaced with natural log (canceling a factor of 1/log(2) from both sides).

xlog(x)=60*1000*log(1000)

To finish it off, you need xe^x on the left hand side so that you can apply the product log function.

e^xlog(x)=xe^x=e^{60000log(1000)}

x = W(e^{60000log(1000)})

About 40,000 evaluated by wolfram alpha.

If we compare it to the simpler case where time complexity is just N, we would have 1000 input completed in 1 minute times 60, for 60,000 completed in the hour. 40,000 means the nlogn process is slowing down slightly for larger inputs due to logn term as we would expect.