algorithm - how many times will a function be executed? -
i have piece of code
for ( = 0; < n ; i+=3 ){ foo(); if( % 5 ==0) foo(); }
and decide how many times foo() executed. have options
ceil(n/3)+floor(n/5) ceil(n/3)+ceil(n/5) floor((n+2)/3)+floor((n+14)/15) floor(n/3)+floor(n/5) floor(n/3)+ceilt(n/5)
what right way deciding right outcome? outer loop executes foo() outside of condition n/3 times , how decide how many times condition execute function?
just make easier understand can split cycle 2:
for ( = 0; < n ; += 3 ){ foo(); } ( = 0; < n ; += 15 ){ foo(); }
for natural n , k cycle (i=0; i< n; += k) run 1 + floor((n - 1)/k) times.
this way total number of runs be: 1 + floor( (n-1) / 3) first , 1 + floor( (n-1) / 15) second cycle is:
2 + floor((n-1) / 3) + floor((n-1) / 15)
Comments
Post a Comment