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

Base, 123 is not valid in which base value

123 is not valid in which base value

Explain the common properties of nurbs surfaces, Question 1 What are the a...

Question 1 What are the advantages of Computer Interactive Graphics? Question 2 Which are the different types of camera views available in Maya? Question 3 Explain

Eeprom, Ask queswhat is the advanages of eeprom?

Ask queswhat is the advanages of eeprom?

Static ram, STATIC RAM: Flip-Flops are the basic memory cells in a stat...

STATIC RAM: Flip-Flops are the basic memory cells in a static RAM. Each flip-flop is based on either two bipolar transistors or two Metal Oxide Semiconductors Field-Effect Tra

Explian, explain anatomy of digital coputer

explain anatomy of digital coputer

What do you mean by geo stationary orbit, Question 1 . Explain (a) Scatter ...

Question 1 . Explain (a) Scatter loss                                (b) Aperture medium coupling loss Question 2 . What do you mean by Geo stationary orbit? Question

Data base software, Data Base Software: Another major type of applicat...

Data Base Software: Another major type of application comes under the heading database software; which allows for the collection of, searching for and manipulation of informat

Briefly explain formatting tool bar, Question 1 Briefly explain the classi...

Question 1 Briefly explain the classification of the computers Question 2 What is arithmetic logic unit? How it is helpful in CPU Question 3 How do you install a new pri

Obtain the truth table and a boolean expression, Problem 1. Convert the...

Problem 1. Convert the following number system 12.34 (8) to binary number system 23BC.0A (16) to decimal number system 456.012 (16) to Octal number system 123

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