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

Data transmission, Data transmission: Most digital communication data i...

Data transmission: Most digital communication data is transmitted in a serial form, that is, only one bit at a time. Transmission of data in serial form means each bit is tran

Kirchhoff’s law, A car battery is of 12 V. Eight dry cells of 1.5 V each ...

A car battery is of 12 V. Eight dry cells of 1.5 V each connected in series can give 12 V. But such cells are not used in starting a car. Why?

Why we need data mining? Give an example to illustrate your, Why we need da...

Why we need data mining? Give an example to illustrate your answer.

FEMAL. REPODUCATIVE. SYSTEM, Ask question #Minimum. Hello. ser can. y...

Ask question #Minimum. Hello. ser can. you. tell. me. that. what. is. the. batter. side. for. BIOLOGY. Students. from. class. 12. / xii. 100 words accepted#

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

Cp, I NEED FLOW CHART ANT DRAWINGS OF BASIC OPERATIONS OF COMPUTER

I NEED FLOW CHART ANT DRAWINGS OF BASIC OPERATIONS OF COMPUTER

Artificial intelligence agents, Artificial Intelligence Agents In the ea...

Artificial Intelligence Agents In the earlier teach, we discussed what we will be talking about in Artificial Intelligence and why those tasks are important. This lecture is all

Defining conditional operator, Problem 1 What is conditional operator? ...

Problem 1 What is conditional operator? Using conditional operator find a smallest number between two numbers Defining conditional operator Using it to find smallest n

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