0
$\begingroup$

Can anyone suggest a starter book or website where I can find information and examples of putting functions under summation signs into Big Theta. basic Arihmetic , geometric, Quadratic are fine , but I would like to work on examples like $$\sum_{i = 1}^{\log n} i \cdot n \text{ or } \sum_{i = 1}^{\log n} 10^i$$

$\endgroup$
1
  • $\begingroup$ $\sum_{i=1}^{\log n} i n = n \sum_{i=1}^{\log n} i$ is an arithmetic series (and $n \sum_{i=1}^{\log n} i = \Theta(n \log^2 n)$) . $\sum_{i=1}^{\log n} 10^i$ is a geometric series (and $\sum_{i=1}^{\log n} 10^i = \Theta(n^{\log 10})$). $\endgroup$
    – Steven
    Feb 26 '21 at 11:22
0
$\begingroup$

Take a look at Appendix A in the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.

Besides you say that you'd like to know how to handle summations besides arithmetic and geometric series (and others) but the two examples you provide are (essentially) an arithmetic and a geometric series.

$\endgroup$
1
  • $\begingroup$ Thank you. just had a quick look and that seems to fit. I failed to realise that I can take the n outside the summation as it is i that is the series . Thank for the guidance. much appreciated $\endgroup$
    – david
    Feb 26 '21 at 13:13
0
$\begingroup$

A nice, reasonably rigourous, self-contained text is Hildebrand's "Short Course on Asymptotics" (it goes into mathematics applications, not computer science). It covers quite a bit more than summations.

$\endgroup$
1
  • $\begingroup$ Thank you for the recommendation $\endgroup$
    – david
    Mar 1 '21 at 10:10

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.