-1
$\begingroup$

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)?

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

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.)

$\endgroup$
  • $\begingroup$ How would I do the second one however kind sir. $\endgroup$ – Fernando Martinez May 5 '13 at 16:57
  • $\begingroup$ In the same way that you did the first. Don't expect me to solve the question for you. Once you really understand the first part, you will be able to solve the second part on your own. $\endgroup$ – Yuval Filmus May 5 '13 at 17:02
  • $\begingroup$ Hmm I see I understand the first one but not the second would I do C lg=10 sec and n is 100 and the do C ln(500) would this be correct, if not would you kindly tell me how to solve it? $\endgroup$ – Fernando Martinez May 5 '13 at 17:11
  • $\begingroup$ I think at this stage it is better if you tried solving the question on your own, using the guidance in my answer if you find it helpful. You only truly understand the subject if you can be confident in your own solution. $\endgroup$ – Yuval Filmus May 5 '13 at 17:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.