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

What is mixing, Question 1 Briefly explain waveform Characteristics ...

Question 1 Briefly explain waveform Characteristics Question 2 Write a note on: types of Microphones Question 3 Briefly explain Magnetic Properties of Audiotape

Amendments in erp, What is new? ERP, on the other hand begins with a fr...

What is new? ERP, on the other hand begins with a fresh relook at the existing business. In fact it is the result of a happy marriage between Business Process Reengineering (BP

Completeness in search - artificial intelligence, Completeness in search - ...

Completeness in search - artificial intelligence: It's also importance trying to calculate the number of solutions to a problem, and the density of those solutions amongst the

Oop, evolution of oop

evolution of oop

Working of web browser, Working of web Browser:   Internet is character...

Working of web Browser:   Internet is characterized by the Client Server Computing that consists of three basic components: The Web client which may be the web browser;

Hotel database, Create a database,show all ojectives and give a fruitful in...

Create a database,show all ojectives and give a fruitful introduction and also state how it will be implemented

Write the function pop in c, QUESTION (a) Convert each of the following...

QUESTION (a) Convert each of the following expressions to prefix and postfix. (i) (A+B)*(C+D) (ii) A-B/(C*D^E) (^ denotes exponentiation) (b) The following algorithm c

What is an array? explain, Question 1 . What is an array? Explain Qu...

Question 1 . What is an array? Explain Question 2 . What do you mean by optional arguments? Describe Question 3 . Describe in brief about interfaces Question 4

Database, #after writing the script of rebuilting indexed on db server it g...

#after writing the script of rebuilting indexed on db server it gave output command executed succesfully does this mean i m done

Methods of working with files, There are two methods to work with files, th...

There are two methods to work with files, the first one is through file control blocks or "FCB" and the second one is through communication channels, also identified as "handles".

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