Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For the following algorithm.

  1. Initialize i = 1.
  2. If i > a then stop. Otherwise, if i divides a then output i.
  3. Increment i by 1, and then go to line 2.

If it takes one unit of time to execute each of the lines 2 and 3 in the above algorithm, how many time units are needed to run the algorithm on inputs of length t (lengths of numbers 1, 10 and 100 are 1, 2, and 3 in that order)? Also, I was wondering how efficient this algorithm is in terms of time.

share|cite|improve this question

If the number $a$ is input, then Step 2 is executed $a+1$ times, and Step 2 is executed $a$ times, for a total of $2a+1$.

If the input is of length $t$, then $10^{t-1} \leq a < 10^t$, hence the worst case running time in terms of $t$ is with $a = 10^t-1$, giving a run time of $2(10^t-1)+1 = 2 \cdot 10^t -1$.

I have no idea what you mean by 'how efficient this algorithm is in terms of time'.

share|cite|improve this answer
I mean, does a run time of 2⋅10^t−1 in the worst case mean that the algorithm is efficient or inefficient. Not sure how to justify either way. – rookie_02 Jul 28 '12 at 9:30
Generally exponential is bad... – copper.hat Jul 28 '12 at 9:38
This analysis does not account for the conditional stop in step 2. So what you get is an upper bound for the worst-case time. In order to show that this upper bound is (in an appropriate sense) tight, I think you need to invoke the infinitude of primes somehow. – Henning Makholm Jul 28 '12 at 10:57
@HenningMakholm: The algorithm only stops when $i>a$? Unless one interprets output as stopping? – copper.hat Jul 28 '12 at 14:36
@copper.hat: Sorry -- I somehow read "output $i$" as "output $i$ and stop". – Henning Makholm Jul 28 '12 at 15:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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