Algorithms, Basic Computer Science

Assignment Help:
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.

Related Discussions:- Algorithms

Languages, Languages The language is a program containing rules and...

Languages The language is a program containing rules and guidelines to help us in making programs. There are various languages like C, Basic, COBOL, PASCAL, FORTRAN etc. Th

Time sharing, Time Sharing Time sharing allows a large number of users ...

Time Sharing Time sharing allows a large number of users at various remote terminals to simultaneously use a centrally located computer for problem solving. Each user operates

Moderns, Moderns: As it was explained earlier, communications channels...

Moderns: As it was explained earlier, communications channels can operate in either the Analog or digital mode. However, a given circuit can operate only in one mode not both

Area of curve, Write a program to find the area under the curve y = f(x) be...

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

As, access,excel and ms word/

access,excel and ms word/

Concept of programming language, CONCEPT OF PROGRAMMING LANGUAGE: In o...

CONCEPT OF PROGRAMMING LANGUAGE: In order to communicate with other human beings, one needs some language or a medium. In the same way for solving problems, a programming  lan

History of e-mail, History of E-mail: Internet based E-mail system was...

History of E-mail: Internet based E-mail system was designed by a Computer engineer - Ray Tomlinson in late 1971 while working with ARPANET. Tomlinson used a file transfer pro

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd