Running time of a function of n

Question

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).

Answer 1

"$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$?

Answer 2

Here would be my suggested guidelines:

If there is a for loop that repeats $n$ times, this is a linear complexity $Θ(n)$ as it will occur that many times.

If there is a for loop that repeats $log(n)$ times, this is logarithmic complexity $Θ(log(n))$ for the same reason.

If a loop repeats a constant number of times, then this is $Θ(1)$ complexity as it doesn't matter what size $n$ is.

As loops are within loops, this should be multiplied together as each is repeating for the next in the chain.

As an example, you could probably do a big-O of $O(n log(n))$ to give the upper bound as half of what you have to prove here. That would be my suggestions for a starting point.

Sorting would be a well studied problem if you want an example to help you here.