algorithm - Breakdown of the cost and time required for Fizzbuzz in worst case -

the fizz-buzz function (in pseudocode) takes positive integer n. i'm curious algebraic breakdown of cost , time required of if-else statement. know worst case running time o(n).

fizz-bizz(n)   = 1 n     if (n % 3 == 0)       print "fizz"     if (n % 5 == 0)       print "buzz"     if (n % 3 != 0 , n % 5 != 0)       print n 

example of breakdown of algorithm:

the time complexity o(n) because if statement has no real effect on that. complexity of if statement constant on large enough dataset.

the if statement may different amount of work in iterations have multiple of 3 or 5 but, amount of work per loop iteration not dependent on n. in fact, averages out constant n becomes bigger.

and, aside, think code may wrong. @ multiples of fifteen, should print both fizz and buzz.

if want level in edit (the added breakdown), need assign arbitrary cost ci each statement (and cost constant single execution of statement) figure out how many times each statement run.

for example, first if sequence runs n times, print "fizz" runs one-third of those, n/3. end table:

                           cost   times fizz-buzz(n)   = 1 n           c1     n     if (n % 3 == 0)        c2     n       print "fizz"         c3     n / 3       [call a]     else       if (n % 5 == 0)      c4     n -         print "buzz"       c5     (n - a) / 5 [call b]       else         print n            c6     n - - b 

add of per example (substituting n-equations a , b) and, in end, you'll still end dependent on n, hence o(n) algorithm. it'll like:

  c1*n + c2*n + c3*n/3   + c4*(n-a)   + c5*(n-a)/5     + c6*(n-a-b) = c1*n + c2*n + (c3/3)*n + c4*(n-n/3) + (c5/5)*(n-n/3) + c6*(n-n/3-(n-n/3)/5) = c1*n + c2*n + (c3/3)*n + c4*(2/3)*n + (c5/5)*(2/3)*n + c6*(n-n/3-(n-n/3)/5) = c1*n + c2*n + (c3/3)*n + (c4*2/3)*n + (c5*2/15)*n    + c6*(n*8/15) = c1*n + c2*n + (c3/3)*n + (c4*2/3)*n + (c5*2/15)*n    + (c6*8/15)*n     /             1         2             2                8    \ = ( c1  + c2   + - c3    + - c4       + -- c5          + -- c6  ) * n    \             3         3            15               15    / 

all values inside parentheses in fact constants (since they're multiples of constants) whole thing constant multiplier of n.

now, if find minor mistake in equations above, wouldn't too surprised - haven't done level of math quite few years, , may have thrown in furphy in case homework , try copying verbatim :-)

but mistake you're find value of constant multiplier itself. still constant multiplier of description, i'll guarantee that.