Provide a tight Θ bound on the running time of the function of n.
for a=1 to n
for b=1 to lg(n)
for c = 1 to 23
x = 2x
My thinking in solving this problem was "x=2x" is a constant so it would be only occur 23 times. I believe this will just cancel out to be some constant?
Currently my answer is $\sum_{a=1}^n \sum_{b=1}^{\lg(n)} \sum_{c=1}^{23} (x=2x)$
Can someone provide me with some guidance for this algorithm analysis question and in simplifying? (I am currently trying to learn latex to post it).
Best Answer
"$x=2x$" has nothing to do in your running-time -- it is something the function does, and doesn't say how long it takes to do it.
If we suppose that multiplication and assignments both take constant time, each execution of
x=2x
will take some fixed time $t_0$. So you need to figure out how many times that is executed. $23$ is not the answer here -- the doubling happens 23 times each time the body of theb
loop runs!If you don't worry about fancy notation for the moment, how would you compute the number of executions of
x=2x
for some concrete value of $n$ -- for example, $n=64$?