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

Cryptography, Consider the one-time pad encryption scheme to encrypt a 1-bi...

Consider the one-time pad encryption scheme to encrypt a 1-bit message m, and assume m is chosen with uniform distribution from message space M={0,1}. Let E1 be the event "message

Global positioning system, How does GPS work in the field of Sport or athle...

How does GPS work in the field of Sport or athletics?

Super computers, Super Computers: The specialised demands and requirem...

Super Computers: The specialised demands and requirements of science, industry and military have led to the creation of powerful super computers. For numerically intensive com

Software, Software Computer cannot be used without a software in...

Software Computer cannot be used without a software in it. It is the software which gives instructions to the hardware of the computer so as to work all devices in tande

Flowchart, Fahrenheit to celsius convertion

Fahrenheit to celsius convertion

How do you insert a symbol in a word document, Fundamentals of IT 1. Ho...

Fundamentals of IT 1. How do you insert a symbol in a Word document? 2. Explain absolute cell addressing? 3. Discuss Custom List? 4. Explain applications of Multimedia

Idk, A rock weighs 33.6 N on Planet X and 49 N on Earth. What is g on Plane...

A rock weighs 33.6 N on Planet X and 49 N on Earth. What is g on Planet X

Differentiate between a dynamic and a static web site, QUESTION a) Diff...

QUESTION a) Differentiate between a dynamic and a static web site. b) Why are electronic mails (e-mails) preferred to the post office mails? How do they affect the modern of

Programmable rom (prom) , PROGRAMMABLE ROM (PROM): The user can program...

PROGRAMMABLE ROM (PROM): The user can program a PROM after purchase.  Each memory bit element in the PROM contains a nichrome or silicon link that acts as a fuse.  The user can

Display the item in red colour on a web page, QUESTION (a) Give the app...

QUESTION (a) Give the appropriate syntax to implement a Client-Side Image Map, specifying all possible attributes where required (b) List the benefits of using Cascading Sty

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