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

Array, An array A is said to be special if all its elements are same. Given...

An array A is said to be special if all its elements are same. Given an array, your task is to convert the array to special array by performing some operations. The allowed operati

What are the various skills needed for broadcasting and film, Question 1 W...

Question 1 What are the various skills needed for broadcasting and film? Question 2 What is a 2 dimensional animations and 3 dimensional animations? Question 3 Different

Integers, what is the size of a void integer and what is it''s range

what is the size of a void integer and what is it''s range

Block matching algorithm, I am using block matching algorithm to get the mo...

I am using block matching algorithm to get the motion vectors, now, how can I get the depth map/depth value from the motion vectors?

Flowchart, create a flowchart showing average score for the 3 quizzes assum...

create a flowchart showing average score for the 3 quizzes assume that there are 3 sections each having 5 students the only valid number to be entered is 1-100 for the quizzes shou

Network engenering, What role would you assign to each of the four workstat...

What role would you assign to each of the four workstation and any other equipment

Sma* search - artificial intelligence, SMA* Search-Artificial intelligence ...

SMA* Search-Artificial intelligence IDA* search is good from a memory point of view. actually it may  be criticised for not using enough memory - utilizing  more memory may inc

Convert string to super ascii, A string S is said to be "Super ASCII", if i...

A string S is said to be "Super ASCII", if it contains the character frequency equal to their ascii values. String will contain only lower case alphabets (''''''''a''''''''-'''''''

Memory, what is cache memory

what is cache memory

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