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
A Patient Registry Name, Surname and Address  Sex  Caste  Contact Numbers  Area (Rural/Urban/Suburban)  City/District  State  General Examination deta

Question (a) A firm produces four products: P , Q , R , and S . Each unit of product P requires two hours of milling, one hour of assembly, and $10 worth of in-process in

THE SECOND GENERATION (1956-1965) This generation of computers were characterized by:     Considerable reduction in physical size     Increased reliability

each of the following functions has the form f(x ) = (ax+b) mod n. assume that each function has type N base n arrow N base n, so that we can think of f as a cipher for an alphabet

Question 1 Explain the different categories of Software applications Question 2 Write a note on Data Dictionaries Question 3 Explain the following (a) Top-down testin

what is multiplaxer and truth table, digram

The easiest way to approach pipelining is to regard as the three stage fetch, decode and execute instruction execution cycle outlined earlier. There are times during each of these

definition of file operations

write a 2 page essay operational gaming and monte carlo simulation

Process of Data mining Data mining is an iterative process that typically involves the following phases: Problem definition A data mining project starts with the understanding o