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$$
$\begingroup$
$\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$– StevenFeb 26, 2021 at 11:22
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\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$– davidFeb 26, 2021 at 13:13
$\begingroup$
$\endgroup$
1
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.
