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
Time Sharing System: With the use multiprogramming, the batch processing can be quite  efficient. However, for many jobs, it is desirable to provide a mode in which the user i


main task of sofware developper

solution of two degree of freedom system with matlab program???

Problem 1 What is precedence of operators? How are expressions evaluated using precedences? Defining precedence of operators Explanation of how expressions are evaluat

Question 1 Draw the block diagram of von Neumann Architecture and explain about its parts in brief Question 2 Draw the block diagram of Intel 8085 CPU organization and explai

Consider the one-time pad encryption scheme to encrypt a 1-bit message m, and assume m is chosen with uniform distribution from message space M={0,1}. Let E1 be the event "message

#questioPurpose of this assignment: 1. Using dictionaries. Assignment: Write a program to read a text file and create a dictionary. The keys for the dictionary should be all

Mike sells on the average 15 newspapers per week (Monday – Friday). Find the probability that 2.1 In a given week he will sell all the newspapers