Consider the following two programs $($where $/$

denotes integer division$)$

$($a$).$ x $0$

for k $$ n down to $1$ do

p $$ k

while p $>1$ do

p $$ p$/5$

x $$ x $+1$

$($b$).$ x $0$

for k $1$ to $2$n do

p $0$

s $$ k

while p $<=$ s do

p $$ p $+2$

x $$ x $+1$

Assume that arithmetic operations take constant time, no matter the size of the operands. For these two

programs

$1.$ Estimate the running time of the inner $($while$)$ loop respect to k for program in $($a$)$ and $($b$).$ You

should give a tight bound, of the form $\backslash$Theta $($f$($k$))$ with f as simple as possible, but you do not need to

justify your answer. $[10$ points$]$