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

Gui design, how to load a video using push button in gui design click

how to load a video using push button in gui design click

Define procedure of Building Assembler programs, In order to be able to mak...

In order to be able to make a program, quite a lot of tools are needed: Earliest an editor is used to create the source program. Next a compiler, which is nothing more than a progr

Software, Software: A computer system consists of two parts - hardware...

Software: A computer system consists of two parts - hardware and software. The first part, computer hardware, refers to all the visible components of the computer system:  key

Vector processing, what are the chrateristics of vector processing

what are the chrateristics of vector processing

E-mail, E-MAIL: Internet has changed the art of writing letters to ema...

E-MAIL: Internet has changed the art of writing letters to email.  Email is one of the ways on Internet to send messages to another person across the network. E-mail and posta

Stub cables, Stub cables: The stub cables are for bi-directional data m...

Stub cables: The stub cables are for bi-directional data movement between LRU and current mode coupler.  The stub cables also supply power from the LRUs to the current couplers

Cisc, two characteristics og CISC architecture?

two characteristics og CISC architecture?

What is the delay of the filter, QUESTION We wish to use the Kaiser win...

QUESTION We wish to use the Kaiser window method to design a discrete-time filter with generalized linear phase that meets specifications of the following form:

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