Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Running time of amstrong algorithm

, ,
Problem Detail:

I have a problem how to find best, worst, average case in armstrong number algorithm?

Here the pseudo-code :

``Declaration:       n : integer       Sum : integer       Temp : integer       Rem  : integer Algorithm:       Input(n)       Temp <-- n       Sum <-- 0       Rem <--- 0       While ( n != 0 ) do                Rem <-- n mod 10                Sum <-- Sum + Rem * Rem * Rem                n <-- n / 10       Endwhile        if ( Sum = n ) then          output (n ," is Armstrong number")      else          Output(n," is not armstrong number")          Endif ``

I find

Best-case : Tmin(n) = 3,

Worst-case : Tmax(n) = 3n,

Average-case : Tavg(n) = 3 [ n(n+1)/2 ] / n = 3(n+1)/2 = 3n+3/2

Sn= n(n+1)/2 The sum of the natural numbers from 1 to n

Thanks for you help.

#### Answered By : Rick Decker

Essentially, the only thing that affects the run time of your algorithm is the loop. This will iterate for as many times as it takes to get from \$n\$ to 0 by dividing \$n\$ by 10. So we're asking, how many times will it be before \$n, n/10, n/100, n/1000, \dotsc\$ gets to 0? That is, when is \$n/10^k = 0\$? Clearly, when \$k=\log_{10}n\$. The loop is unaffected by any difference between the \$n\$ values, as long as they have the same number of decimal digits, so best-case time = worst-case time = average-case time = \$3\log n\$ plus some constant overhead for setting the variables and displaying the output.