Algorithms, Basic Computer Science

1. In each of the following situations, indicate whether f = O(g), or f = O(g), or both (in which case f = T(g)). Briefly explain why.
(a) f(n)=10n5 +8n2,g(n)=20n4 +7n3 +300 (b) f(n) = log 8n, g(n) = log(n2)
(c) f(n)=n3logn,g(n)=13n 5
(d) f(n) = (3)n, g(n) = 6n3 2
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-O notation, show that 3n + 5 = O(n) and n = O(3n + 5), in other words, 3n + 5 = T(n).
3. The Fibonacci numbers F0, F1, F2, . . ., are defined by the rule F0 =0,F1 =1,Fn =Fn-1 +Fn-2.
Use induction to prove that Fn = 20.5n for n = 6.
4. Write a python program to compute the Fibonacci numbers F8, 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.
Posted Date: 9/11/2012 10:02:47 PM | Location : United States







Related Discussions:- Algorithms, Assignment Help, Ask Question on Algorithms, Get Answer, Expert's Help, Algorithms Discussions

Write discussion on Algorithms
Your posts are moderated
Related Questions
QUESTION (a) Distinguish between S-HTTP and SSL (b) What are the three basic security provided by SSL? (c) Discuss the limitations of SSL (d) State the port number us

Completeness in search - artificial intelligence: It's also importance trying to calculate the number of solutions to a problem, and the density of those solutions amongst the


QUESTION (a) Give the appropriate syntax to implement a Client-Side Image Map, specifying all possible attributes where required (b) List the benefits of using Cascading Sty

what are the definition?

what is the sql command to List all the join conditions or join paths (pairwise) existing between tables.

Client/ Server Architecture:   As the capacity and power of personal computers improved, the need to share the processing demands between the host server and the client workst

QUESTION 1 Write short notes on controlled vocabulary indexing. QUESTION 2 (a) List five types of abstracts. (b) Describe four types of abstracts. QUESTION 3

hitory and genration of computer