# Time units needed to run factor finding algorithm on inputs of length t and time efficiency

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.

-

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