Hello math01!
Here are the answers to your questions.
a) 1+2+4+8... n times can be written, using the Sigma notation, as
n
___
\
/ 2^i
---
i=0
where ^ means "to the power of". Therefore, this sum would be 2^0 +
2^1 + 2^2 + 2^3 + ... = 1 + 2 + 4 + 8 + ...
as you can see in the following document (you'll need Acrobat Reader
in order to read it), this sum amounts to 2^(n+1) - 1, which is equal
to 2*(2^n)-1.
Analysis of Algorithms (see page 4)
http://www.cs.aucegypt.edu/~mudawwar/csci210/slides/Analysis.pdf
Therefore, the expression is O(2^n). Notice that the "dominant" term
in each expression is used for the big O notation. Check the following
pdf document to see which terms dominates others.
Algorith Analysis
http://courses.cs.vt.edu/~cs1704/fall02/Notes/C12.AlgorithmAnalysis.pdf
b. As you can see in the first pdf document cited above, the sum
1+2+3+...+n
amounts to n*(n+1)/2, which gives [n^2+n]/2. But you're then
multiplying this expression by n, thus arriving to [n^3+n^2]/2. As
before, the term used for the tightest big-O notation is the dominant
one; in this case, n^3. Therefore, the tightest big O notation for
this expression is O(n^3)
c. I assume here that the expression here would be log(n^2) +
2*log(n). Please do tell me through a clarification request if I'm
wrong with this assumption. We can use here that log(n^k)=k*log(n) (k
being a constant). Therefore, log(n^2)=2*log(n), so the expression
becomes 2*log(n)+2*log(n)=4*log(n). Clearly, the big-O notation in
this case is O(log(n)).
d. I'll make a similar assumption here. I think the expression you
meant to ask about is:
1^2 + 2^2 + 3^2 + ... + n^2
Again, this sum is considered in the mentioned pdf document (it's the
second expression in page 4). This sum becomes n(n+1)(2n+1)/6 or,
equivalently,
2n^3 + 3n^2 + n,
in which the "dominant" term is n^3. The tighest big-O notation is
thus in this case O(n^3).
For more information on this subject, also see
Analysis of Algorithms: Motivation...
http://www.cs.bris.ac.uk/Teaching/Resources/COMS11101/9_Complexity.p.pdf
Google search strategy
tighest big-O notation
://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=tightest+big-O+notation
I hope this helps. If you have any doubt regarding my answer, please
request a clarification before rating it. Otherwise, I await your
rating and final comments.
Best wishes!
elmarto |
