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

Process control management, Process Control Management:   A  process  ...

Process Control Management:   A  process  is an executing program. It is considered the standard unit of work within a computer system. Every executing program is treated as a

C++ programming, write a program of 2 sum and 2 product number in C++ progr...

write a program of 2 sum and 2 product number in C++ programming language

Fully describe the assessment centre method of selection, Problem: One ...

Problem: One large employer requests CVs from applicants, and, on the basis of these, invites a selected number to take part in a telephone interview. A date and time are provi

Basic of simulation, Task 1 Study various types of systems and simulate a s...

Task 1 Study various types of systems and simulate a system of your own. Task 2 Study various models and enumerate the various steps for designing a corporate model

Bandwidth, Bandwidth: Bandwidth is the second concept important for tr...

Bandwidth: Bandwidth is the second concept important for transmission. This concept can be explained with the help of the traffic network mentioned earlier. If there is a two-

Message quality and quantity, Message Quality and Quantity: Quality of...

Message Quality and Quantity: Quality of transmission is a very important .consideration in telecommunication. Voice communication can use a narrow bandwidth, which means the

CAI, What is CAI? Explain its pitfalls

What is CAI? Explain its pitfalls

What is the intent of the singleton pattern, QUESTION Consider a Univer...

QUESTION Consider a University system which has several sub systems: Student Registration Module Registration Time Tabling Library System Human Resource Manag

Define the elements of contlor unit , The three main elements of the con...

The three main elements of the control unit are: 1. Decoder this is used to decode the instructions that create a program when they are being processed, and to establish in what ac

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