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
Hi? are you conversant with Java that is J2SE 6 coz i have assignments on this area?

Uniform Path Cost Search-Artificial intelligence A breadth first search will search the solution with the shortest path length from the first state to the goal state. Though, t

Types of chat room: Java Chat rooms: The most common and popular chat scripts are based on java which is object oriented language. Java is freely available and comes with virt

QUESTION (i) Define each of the following terms: a) Interlibrary lending b) Manuscript c) Papyrus d) Community profile e) Mauritiana (ii) Explain with example

Question 1 List the Basic essential components of a computer network Question 2 What are the functions of (i) Routers (ii) Bridges Question 3 What are the advantag

Machines which exhibit intelligent nature Machines in this case could easily be personal computers, or they could be robots with embedded systems, or a combination of both. Wh

Spreadsheet Software : Consider the grid in Fig. 9.4. It is split into rows and columns and is a pictorial representation of a typical spreadsheet program.  Figure: Spr

Technology Partnerships: Such agreements provide the consumer un-limited access to vendor's technology. Such contracts are typically multi-year in nature where the consumer pa

Concept of instruction: The CPU is a semiconductor integrated  circuit chip consisting of a large number of transistors. In personal computers, the CPU is also referred by the

sum of first 100 integers