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

Subroutine , Subroutine :   A subroutine  is a type of subprogram, a pi...

Subroutine :   A subroutine  is a type of subprogram, a piece of code within a larger program that performs a specific task and is relatively independent of the remaining code.

Unix, How do I change file permissions? Every time I execute chmod commands...

How do I change file permissions? Every time I execute chmod commands it tells me permission denied.

Microprocessor, what is computer? explaine the block diagram of a general p...

what is computer? explaine the block diagram of a general purpose digital computer.

List two i/o virtualization methods, Question 1 List two I/O virtualizatio...

Question 1 List two I/O virtualization methods. Based on different features compare these two methods Question 2 Discuss three areas considered by organizations to secure the

Enterprise resource planning, ENTERPRISE RESOURCE PLANNING What ...

ENTERPRISE RESOURCE PLANNING What has football got to do with it? asks management guru Michael Hammer in his latest best seller Beyond Reengineering. The answer is almos

Knowledge of the environment of ai system, Knowledge of the Environment ...

Knowledge of the Environment We must distinguish between knowledge an agent receives through it's sensors and knowledge about the world from which the input comes. Knowledge a

Explanation of components of excel work book, Problem 1 Briefly explain...

Problem 1 Briefly explain Components of Excel Work book Explanation of Components of Excel Work book Problem 2 How do you insert a watermark in the Word docume

Application packages, APPLICATION PACKAGES : There are two options. You ca...

APPLICATION PACKAGES : There are two options. You can either write your own program or buy an applications package, i.e. a proprietary program, 'off-the-shelf. The former option i

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