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
    @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