I have the following algorithm:
func()
{
for(i=1; i<n; i=i*2)
print("aa");
}
How can I find Big-Oh using summation?
I have the following algorithm:
func()
{
for(i=1; i<n; i=i*2)
print("aa");
}
How can I find Big-Oh using summation?
Finding a suitable sum here is a bit awkward since sums in mathematics tend to step up by one, always. So we have to normalize the sequence of values of i
$\qquad i = 1, 2, 4, 8, \dots [i<n]$
to
$\qquad i' = 0,1,2,3, \dots [???]$.
My notation already suggests that it's about finding the right termination predicate.
Roughly speaking, you're looking for the inverse operation to the repeated step function, which by itself is $i \mapsto 2i$. I'm not sure how to lead you towards an answer unless you know about logarithms. If you do, it should be kind of obvious; roughly:
$\quad i' = 0,1,2,3, \dots [i'<\log_2 n \pm 1]$.
Do some tinkering to find out whether you need to use $\lfloor \log_2 n \rfloor$ or $\lceil \log_2 n \rceil$ as upper bound on $i'$. Now, the rest is elementary.
Note that you can go about this by normalizing the for
loop first:
for(i=1; i<n; i=i*2)
print(i)
becomes
for(i' = 0; i' < log(2,n) +- 1; i'++)
print(2^i');
Note that for functional equivalence, I start with $i'=0$ so that $2^{i'} = i$ in each iteration; you can also use $2^{i'-1}$ instead and start with $i'=1$. Try out a few things -- some make the code nicer, others the mathematics afterwards.
Make sure -- by proof and/or testing -- that the normalized loop computes exactly the same thing as the old one, and then it's all standard. You might need a cheat sheet to simplify the sum.
Summation is not the correct technique here. The running time is proportional to the number of loop iterations, which is the number of times you have to double 1 until you reach $n$ (or more). For example:
And so on. It remains to relate $n$ to the number of iterations of the loop.
It is possible to express the number of iterations as an infinite sum: $$ T(n) = \sum_{k=0}^\infty [\![n > 2^k]\!], $$ where $[\![n > 2^k]\!]$ is $0$ if $n \leq 2^k$ and $1$ if $n > 2^k$. However, I'm not sure that this representation brings us any closer to finding the formula $T(n) = \lceil \log_2 n \rceil$.
for
-loop better be.
$\endgroup$