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

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

-
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