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 Decode or execution cycle?, just the once the instruction has bee...

just the once the instruction has been fetched and is accumulated, the next step is to decode the instruction so as to work out what actions should be performed to execute it. This

Computational physiology, Estimate the mean deflection of the QRS complex i...

Estimate the mean deflection of the QRS complex in each of the six standard leads (I, II, III, aVR, aVL, aVF) in Figure 1 and then estimate the mean heart vector for the normal hea

Explain data movement ?, In any program it is essential to move the data in...

In any program it is essential to move the data in the memory and in the CPU registers; there are a number of ways to do this: it can copy data in the memory to a number of registe

Explanation pre increment with example, Problem 1 What is precedence of...

Problem 1 What is precedence of operators? How are expressions evaluated using precedences? Defining precedence of operators Explanation of how expressions are evaluat

Memory of computer, Memory : Computers store information internally as wel...

Memory : Computers store information internally as well as externally. Linked to CPU is an internal memory unit where all the instructions and data are stored. It contains the

IPC in linux, to do a assignment regarding IPC in linux

to do a assignment regarding IPC in linux

E - R diagram, draw the e r diagram for irctc rail ticket reservation onlin...

draw the e r diagram for irctc rail ticket reservation online

Adding macros to ms word 2010 for a particular format, Project Setting up ...

Project Setting up Microsoft Word 2010 to automatically handle as much as possible of the NDSU Graduate School requirements for a disquisition. Accessible from the Graduate Schoo

Network, Give a topology (network diagram) in which there is a link whose f...

Give a topology (network diagram) in which there is a link whose failure will change many routes. Give one in which there is a link whose failure will not change any routes

Qbasic, write a program of circle of any colour

write a program of circle of any colour

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