0
$\begingroup$

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.

1 Answers 1

1

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

  • 0
    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.2012-07-28
  • 1
    Generally exponential is bad...2012-07-28
  • 0
    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.2012-07-28
  • 0
    @HenningMakholm: The algorithm only stops when $i>a$? Unless one interprets output as stopping?2012-07-28
  • 0
    @copper.hat: Sorry -- I somehow read "output $i$" as "output $i$ and stop".2012-07-28
  • 0
    @HenningMakholm: No problem at all; the computation you suggest is a much more interesting one (and out of my range)...2012-07-28
  • 0
    @copper.hat Under Henning's interpretation, the algorithm will run in constant time, since it will stop when $i=1$. Very efficient, but not particularly useful.2012-08-27