Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm not sure if this is the best place for this question, since it's programming related, but unfortunately, I don't have a better idea right now (CS looks too high level and I don't want to focus on implementation). I hope I managed to bring it down form computer science problem to a purely mathematical problem.

Anyway, I've got code that looks something like this:

a=1;
b=n;
while (a < b) do
{
        for i=1, i < a, i++ do
        {
            /* blah blah, this is constant c*/
        }
        a=a*3;
        b=b/2;
}

I'm supposed to calculate the exact computational complexity (the minor stuff related to while and for loops isn't important in this question).

Now I know that the while will repeat a certain number of times and that number will be a logarithm and that's not the problem. My problem is the for loop part. I know that each time the loop repeats, I'll get $ \sum_{i=1}^{a} c $ repetitions of c and that sum will repeat $ \log_{6}{n}-1 $ times.

If the $a$ didn't change, I'd get $ac( \log_{6}{n}-1)$. Since I have constant in the sum, I could just multiply the constant by the upper bound and then multiply that by the number of times the whole sum will repeat.

In this case, however the upper limit of the sum changes each time. So how do I exactly calculate he number of times the $c$ gets added to itself?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

I'll trust your conclusion about the outer iteration count being $\log_6 n-1$ -- it seems to me that there's a probably fencepost error somewhere there, but I'll not go looking for it (since it won't affect the eventual result). For brevity, let's set $k=\log_6 n - 1$.

In the first iteration through the outer loop, the inner one executes 1 time. The next time it executes 3 times. The next one it executes $3^2$ times, and so forth up to $3^{k-1}$ times. So for the total number $x$ of executions of the inner loop body we have $$x=1+3+3^2+\cdots+3^{k-1}$$ Let's take that equation and multiply both sides with 3: $$3x=3+3^2+\cdots+3^{k-1}+3^k$$ There's a lot of similar terms there, so subtract the original equation to get rid of them: $$2x=-1+3^k$$ And now we can easily solve for $x$ to get $x=\frac{3^k-1}{2}$.

Ignoring constant factors and minor terms that won't make any asymptotic difference, we get $O(3^{\log_6(n)}) = O(n^{\log_6(3)})$ iterations through the inner loop.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.