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

Asked By : Nezza

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49061

3.2K people like this

 Download Related Notes/Documents