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

Write a long note on the types of charts, Question 1 Write a long note on ...

Question 1 Write a long note on the security features of Windows XP Question 2 Write a long note on computer peripherals, briefly describing some of the devices Question

College management system project, E-R diagram and details for college mana...

E-R diagram and details for college management system

Array, An array A is said to be special if all its elements are same. Given...

An array A is said to be special if all its elements are same. Given an array, your task is to convert the array to special array by performing some operations. The allowed operati

Dataflow modeling for dsp design, Dataflow Modeling for DSP Design The ...

Dataflow Modeling for DSP Design The necessary components in the research of application-specific computer architectures are: 1) a clearly identified set of problems that can b

Grammar, Given the following grammar: -> [ , ] | -> | { } -> a...

Given the following grammar: -> [ , ] | -> | { } -> a | b | cwhich are the strings generated by the grammar? Show the parse tree(s). a). { [ a , b ] }b). [ { a } , b ]

Discuss the advantages and disadvantages of printed indexes, QUESTION 1 ...

QUESTION 1 Discuss the advantages and disadvantages of printed indexes. QUESTION 2 (i) The Library of Congress Subject Headings List and the Sears Subject Headings List

Variable - concept of programming language, Variable - Concept of programmi...

Variable - Concept of programming language: Variable: As referencing memory by its physical address is very tedious, variable names are used. A variable is a symbolic name giv

What is Multilevel Feedback Queue Scheduling?, • Multilevel feedback queue...

• Multilevel feedback queue-scheduling algorithm enables a process to move among queues. It uses a number of ready queues and acquaintances a dissimilar priority with every queue.

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