CSCI 3104: Algorithms Homework 1 Due at1:00pm on Wednesday September 12 2012. Su

CSCI 3104: Algorithms
Homework 1
Due at1:00pm on Wednesday September 12 2012. Submit your solution electronically
athttp://moodle.cs.colorado.eduin PDF format or turn in the paper version before
class. Make sure to include your name student id email address and the Honor Code
Pledge (http://honorcode.colorado.edu/about-honor-code).
In each of the following situations indicate whetherf=O(g) orf= O(g) or both
(in which casef= T(g)). Briefly explain why.
(a)f(n)=10n5+8n2g(n)=20n4+7n3+300
(b)f(n) = log 8ng(n) = log(n2)
(c)f(n)=n3logng(n)=13n
5
(d)f(n) = (3)ng(n) = 6n3
2
We introduced in class that when analyzing algorithm complexity we can ignore the
lower-order terms and the coefficient of the leading term. For example 3n+ 5?n.
Using the formal definition of the big-Onotation show that 3n+ 5 =O(n) and
n=O(3n+ 5) in other words 3n+ 5 = T(n).
The Fibonacci numbersF0 F1 F2 . . . are defined by the rule
F0=0F1=1Fn=Fn-1+Fn-2.
Use induction to prove thatFn=20.5nforn=6.
Write a python program to compute the Fibonacci numbersF8 F28 F48. What are the
three values? What is the total number of additions needed by your program? Provide
your answers as well as your source code.