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

Number system , NUMBER SYSTEM:  We are familiar with decimal number sy...

NUMBER SYSTEM:  We are familiar with decimal number system which uses ten distinct symbols from 0...9, and has base 10. In the decimal number system a number n 4 n 3 n 2 n 1

Stable marriage Problem, How to make a stale marriage program by implementi...

How to make a stale marriage program by implementing the Gale Shapley algorithm using Java program

Optical fibres, Optical Fibres: Coaxial cables have limitations such a...

Optical Fibres: Coaxial cables have limitations such as broadband transmission medium which can be overcome by the use of optical fibres. Optical fibres carry light waves (rep

Communication channels, COMMUNICATION CHANNELS: A wire pair connecting...

COMMUNICATION CHANNELS: A wire pair connecting two telephones is the simplest circuit, allowing communication in both directions. Other channels include coaxial cables, optica

Explain uses of system call and its major types, In computing, a system cal...

In computing, a system call is how a program asks for a service from an operating system''s kernel. This may contain hardware related services (for example accessing the hard disk)

Stack, How to write an algorithm to reverse the order of elements on a stac...

How to write an algorithm to reverse the order of elements on a stack s using two additional stacks

REMOTE DESKTOP, I WANT TO CONNECT A PC WIYH MY PC THROUGH REMOTE DESKTOP. W...

I WANT TO CONNECT A PC WIYH MY PC THROUGH REMOTE DESKTOP. WHAT I DO TELL ME PLEASE

Construct a conditional profits table, Question (a) A dairy wants to de...

Question (a) A dairy wants to determine the quantity of butter it should produce to meet the demand. Past records have shown the following demand pattern:

Backup storage, Backup Storage: Back up (backing) storage, also termed...

Backup Storage: Back up (backing) storage, also termed external storage, is used to hold programs and data which are read into internal storage when required. The most common

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