# Algorithmic analysis using log [duplicate]

How would I solve the following.

An algorithm that is O(Lg_2 n) takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?

An algorithm that is O(n lg_2 n) takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?

For the first one would I do

10/ln(100)/ln(2) times ln(500)/(ln2)?

• you had a very similar question somewhere else. – AJed May 5 '13 at 0:19
• It is a bit different from my previous question becames it is a log order of magnitude. – Fernando Martinez May 5 '13 at 16:43

Let's do the first one. The running time of the algorithm is roughly $C\log n$ for some $C$ (we can "swallow" the base of the logarithm into $C$). When $n = 100$ you know that $C\log n = 10s$. Determine $C$, and then compute $C\log 500$. (You can also use a "shortcut" like the one you're trying to do, but it's more helpful to do it this way, since such a shortcut is harder to come by in the second part of the question.)