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

Hypertext transfer protocol (http), It's a common protocol or "language" co...

It's a common protocol or "language" computers use to "speak" to each other over the Web.

Autonomous rational agents - artificial intelligence, A utonomous Rational...

A utonomous Rational Agents: In many cases, it is not accurate to talk about a particular program or a particular  robot, as the combination of and software and hardware in so

Some CPUs provide multiple modes of operation, even though most systems onl...

even though most systems only distinguish among user and kernel modes, some CPUs provide multiple modes. Multiple modes could be used to provide a finer-grained security strategy.

What are the features of microprocessor ?, Previously two sections the fund...

Previously two sections the fundamentals of the workings and architecture of the central processing unit has been explained. There has been a common look at easy processor architec

Arrays and strings, This is a C file. 1. The program starts by printing you...

This is a C file. 1. The program starts by printing your name with an end sign ">". For example, "NAME >"; 2. Then, you can type in a string. If the string is not "vi xxx", you pri

Defining conditional operator, Problem 1 What is conditional operator? ...

Problem 1 What is conditional operator? Using conditional operator find a smallest number between two numbers Defining conditional operator Using it to find smallest n

ToDoMenu, In this assignment, you should create a class called ToDoMenu whi...

In this assignment, you should create a class called ToDoMenu which has a main method that contains the code that implements a command-line menu for managing a collection of ToDoIt

Digitalelectronics, what duality principle and huntington postulates

what duality principle and huntington postulates

Information system and information technology, What is the difference betwe...

What is the difference between information technology and information systems? Describe some of the fuctions of information systems

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