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

Line decoders, number of 4 to 16 line decoders required to get 8 lto 256 li...

number of 4 to 16 line decoders required to get 8 lto 256 line decoder

Calculate simple interest -algorithm, Algorithm : 1. Read the values of pri...

Algorithm : 1. Read the values of principal amount, time and rate of simple interest into the locations labelled as P, T, R. 2. Set the count T to 1 implying the end of a year. 3.

Overview of a computer system, Overview of a Computer System The...

Overview of a Computer System There are three major elements in every computer solution. They are:     Data     Hardware     Software Hardware + Softwa

Internet searching algorithm, Internet searching algorithm: Searching: Wh...

Internet searching algorithm: Searching: When a user enters a query into a search engine, the engine examines its index and provides a listing of best-matching web pages accordin

Purchasing a database program, When purchasing a database program, you must...

When purchasing a database program, you must have a clear idea of what you need it for. Ask yourself the following questions. (1) Will it perform all (he operations necessary f

Write the steps to use the network setup wizard, Question 1 Elaborate the ...

Question 1 Elaborate the various steps in performing a Mail Merge. Execute one mail merge operation for sending invitation for a conference which is being conducted in your organi

FCB files:Channels of communication , The use of manage files very much fac...

The use of manage files very much facilitates the creation of files and programmer can focus on other aspects of the programming lacking worrying on details which can be handled by

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