- The best essay writing company you will ever find online
- +1(646) 814 8116
- bestessayswriters@gmail.com

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.