Question

find time complexity in terms of n? use big-O

i,j,k,x =0;

for i=0; i<=n; i++;

for j=0, j<=5; j++;

for k=5; k<=n; k=k*5;

x = x*n;

Answer 1

Please find below explanation:

i,j,k,x =0;

for i=0; i<=n; i++; # time complexity for this line is O(n)

for j=0, j<=5; j++; # time complexity for this line is O(5)

for k=5; k<=n; k=k*5; #time complexity for this line is O(5^k)

x = x*n; # time complexity for this line is O(logn)

for k=5; k<=n; k=k*5; #time complexity for this line is 5 power k which is exponential

because every time the loops execute the number will be multiplied by 5 till n times

5*5

5*5*5

5*5*5*5 this will go 5 power k times

5power k>=n

Overall time complexity is (n)*(5)*(5^k)+logn

remove constant 5 above and we get O(n(5^k)+logn) is the time complexity for the above code.