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

Analogue to digital converter, Analogue to digital converter: In an ADC...

Analogue to digital converter: In an ADC a range of input values must correspond to a unique digital word.  The type of code used depends on the system but here only binary cod

Data mining test, Use the methods of C4.5 to design a decision tree

Use the methods of C4.5 to design a decision tree

Fourth generation of computers, THE FOURTH GENERATION (1975 ONWARDS) ...

THE FOURTH GENERATION (1975 ONWARDS) This generation of computers have one or more of the following characteristics:     Semi-conductor memory instead of core memo

Computers in laboratory organisation and management, Computers can be used ...

Computers can be used for better and more efficient management and organisation of laboratories. A computer like the human brain receives information, stores and processes it and t

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

What is the definition of macro?, Definition of the macro A macro is a col...

Definition of the macro A macro is a collection of repetitive instructions in a program which are codified only one time and can be used as many times as required. The major differ

Create a database in access, The following are required: Create a ...

The following are required: Create a project in Access.  Your database must have flow and a theme. The database must be normalized.  The content m

Choice of medium - transmission channels, Choice of Medium: All the tr...

Choice of Medium: All the transmission channels discussed in the foregoing paragraphs can be used as point to point connections or as broadcast systems. Transmitting informati

Flowchart, create a flowchart showing average score for the 3 quizzes assum...

create a flowchart showing average score for the 3 quizzes assume that there are 3 sections each having 5 students the only valid number to be entered is 1-100 for the quizzes shou

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