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
to do a assignment regarding IPC in linux

explian set associte mapping


Gareth's Gardens is a small firm that specialises in planning and laying new gardens.  A particularly popular garden plan consists of a patio and lawn, together with a circular pon

In view of the fact that processes frequently need to communicate with other processes therefore, there is require for a well-structured interaction, devoid of using interrupts, a

Name and explain the classifications of computers

what are daily uses of twisted pair cable in network

IPv6 documented in 1994 (RFC 1752) is still a collection of Draft and Proposed standards Several pre-standard implementations exist IPv6 was intended to be a pragmatic up


Frequency Division Multiplexing : FDM is an analog technique that is applied when he bandwidth of link is greater than the combined bandwidth of the signals to be transmitted. a