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

Operation system, how to create 1000 random processes with time scales betw...

how to create 1000 random processes with time scales between 10 to 400 milliseconds

Basic syntax of python language, The Python language has a lot of similarit...

The Python language has a lot of similarities to Perl, C and Java. Though, there are some specific differences between the languages. First Python Program: relative Mode Programmin

What is fragmentation? explain its significance, Question A What is fragme...

Question A What is fragmentation? Explain its significance Question B Briefly discuss the functions of transport layer Question C What is CIDR? Explain Question D W

Interpreter, Interpreter: An interpreter is a program that translates...

Interpreter: An interpreter is a program that translates each statement in the programming language into machine code and runs it.  Such an arrangement means that to run the

How is the ack request formed, QUESTION a) The handling of the INVITE t...

QUESTION a) The handling of the INVITE transaction in SIP is completely different from the handling of other transactions. The handling of the INVITE is one of the most complex

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.

How to assign Values to Variables in python?, ython variables do not compri...

ython variables do not comprise to be explicitly declared to already reserve memory space. The declaration occurs automatically when you allocate a value to a variable. The equal s

Finding average marks, Problem In the Excel sheet, input the marks of a...

Problem In the Excel sheet, input the marks of any 5 students with 5 subjects and find the average marks, maximum marks, minimum marks obtained by the student. Using Excel s

Data transmission, Data transmission: Most digital communication data i...

Data transmission: Most digital communication data is transmitted in a serial form, that is, only one bit at a time. Transmission of data in serial form means each bit is tran

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