[Math] Running time of a function of n

algorithmsasymptotics

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 the b 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$?

Related Question