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
Knowledge of the Environment We must distinguish between knowledge an agent receives through it's sensors and knowledge about the world from which the input comes. Knowledge a

The technique to mix C and assembly language is to apply the "asm" directive. To access C-language variables from assembly language, you just use the C identifier that name is a me

sum of first 100 integers

Subroutine :   A subroutine  is a type of subprogram, a piece of code within a larger program that performs a specific task and is relatively independent of the remaining code.

Problem 1 Explain the different categories of electronic payment system in detail Listing the types and sub types Explanation Problem 2 We know that there a


READYMADE VERSUS CUSTOM-MADE SOFTWARE Nursing care software can be in two forms. Software can be custom-made with the help of a computer programmer, suited for a client with v

Digital to analogue conversion (dac): Since many systems used on aircraft will require outputs in analogue form, it will be necessary to be able to convert the digital informat

Department (DeptNo, DeptName, Office, Phone) Employee (EmpNo, FirstName, LastName, JobTitle, HireDate, Salary, MgrNo, Deptno) Customer (CustNo, CompanyName, Street, City, State, Zi

Question 1 Describe the following with respect to creating Web Forms in .Net environment- Web Form Life Cycle Creating a Web Form Write programs with corresponding