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
The difference between kernel mode and user mode gives a rudimentary form of security in the following manner. Convinced instructions could be executed only when the CPU is in kern

A hash sign (#) that is not within a string literal begins a comment. All characters later than the # and up to the physical line end are division of the comment, and the Python in

COMMUNICATION CHANNELS: A wire pair connecting two telephones is the simplest circuit, allowing communication in both directions. Other channels include coaxial cables, optica

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

I define a restricted form of TMs M as follows. Given any input x on the tape of M, the initial portion of the tape that holds x is read-only and one-way. That is, M cannot write o

what is computer mapped input / output

how much it cost for 8 week class

For multi-national business IT system, free and open source software (FOSS) is recommended over a proprietary system. The reasons for this recommendation are: 1. Security I

Question 1 Briefly explain principles of effective navigation Question 2 Explain the terms URI and URL. Why should you use Relative URI? Question 3 What are the di

convert the following in to binary 108