1
$\begingroup$

I have the following algorithm:

func()
{
    for(i=1; i<n; i=i*2)
        print("aa");
}

How can I find Big-Oh using summation?

$\endgroup$
  • 1
    $\begingroup$ I saw you post this question before. whatever happened to that one? $\endgroup$ – Apiwat Chantawibul Mar 1 '18 at 10:51
  • $\begingroup$ @Billiska I have created one simpler so not to make confuse others with my proposed solution. $\endgroup$ – J. Doe Mar 1 '18 at 10:53
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 1 '18 at 12:39
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Mar 1 '18 at 12:39
  • 1
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – David Richerby Mar 1 '18 at 18:07
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Succinctly explained, with room for personal discovery ;-) $\endgroup$ – Musa Al-hassy Mar 1 '18 at 16:24
0
$\begingroup$

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:

  • If $n \leq 1$, the loop is run zero times.
  • If $1 < n \leq 2$, the loop is run once.
  • If $2 < n \leq 4$, the loop is run twice.
  • If $4 < n \leq 8$, the loop is run thrice.
  • If $8 < n \leq 16$, the loop is run four times.

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

$\endgroup$
  • $\begingroup$ Yes I have found other solution like to make a table and for each $i$ to evaluate and to find the array of numbers and in the end, I can see that it is $logn$ but I find summation a better and understandable way to express time complexity this is why I'm asking. $\endgroup$ – J. Doe Mar 1 '18 at 10:52
  • $\begingroup$ Summation isn't a panacea. For example, it is completely useless here. How would you solve a quadratic equation using summation, for example? $\endgroup$ – Yuval Filmus Mar 1 '18 at 10:53
  • $\begingroup$ Based on the book of concrete mathematics there are series used to solve the complexity of algorithms. So I want to know which is the best way to solve the complexity and till now I have seen the summation is used mostly in books. $\endgroup$ – J. Doe Mar 1 '18 at 10:56
  • $\begingroup$ Here you have an example for which summation just isn't the way to determine the time complexity. Not everything in mathematics is a sum. $\endgroup$ – Yuval Filmus Mar 1 '18 at 10:59
  • $\begingroup$ @YuvalFilmus Not everything, but the number of iterations of a for-loop better be. $\endgroup$ – Raphael Mar 1 '18 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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