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

Write a program to solve a maze 10x10, write a program to solve a 10x10 maz...

write a program to solve a 10x10 maze. prompt the user for an input text file containing ten rows(ten characters on each row). Use following characters in the input file: * startin

Microprocessors, what is the role of microprocessors in IT? how they are us...

what is the role of microprocessors in IT? how they are used in medical field? how they are used in our real lifes? how they are used in latest technology?

Acting Rationally - artificial intelligence, Acting Rationally: Al Capo...

Acting Rationally: Al Capone was finally convicted for tax evasion. Were the police acting rationally? To answer this, we must first look at how the performance of police force

What is structure, Problem 1 Write a recursive function to find sum of ...

Problem 1 Write a recursive function to find sum of even numbers from 2 to 50 Writing function and explanation Problem 2 What is structure? Explain how structu

Poset , 1. (40 points) Add a course drop method to the system that you impl...

1. (40 points) Add a course drop method to the system that you implemented in Problem Set 1. Modularize your new implementation properly. For any new methods that you introduce: 1.

Function, function of arithmetic logic unit

function of arithmetic logic unit

Definition of algorithm , Definition of  Algorithm  An algorithm is a ...

Definition of  Algorithm  An algorithm is a design or plan of obtaining a solution to a problem. The solution is presented by listing all steps in which they are carried out.

Netlogo, Do you have expert can deal with netlogo

Do you have expert can deal with netlogo

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