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

Synchronizing Threads in python, The threading module offered with Python i...

The threading module offered with Python includes a simple-to-implement locking mechanism that will permit you to synchronize threads. A new lock is formed by calling the Lock() me

Explain the concept of a transition graph, Question 1 Define the concept o...

Question 1 Define the concept of equivalence relation. Give atleast two examples of equivalence relation Question 2 Prove that a graph G is connected if and only if it has a

C++, whats the out put of int main(){ int n=310; funcone(n); functwo(&n); ...

whats the out put of int main(){ int n=310; funcone(n); functwo(&n); cout return 0; } void funcone(intn) n=240; } void func two(intn*) { n=120; }

Write down dijkstra''s algorithm, QUESTION (a) Write down the Update ...

QUESTION (a) Write down the Update Step in the Dijkstra's algorithm explaining its complexity. (b) Propose a Generic Algorithm for Depth-First Search Algorithm, assuming

Create a database in access, The following are required: Create a ...

The following are required: Create a project in Access.  Your database must have flow and a theme. The database must be normalized.  The content m

Virtual memory, What is virtual memory? How address mapping is done in cach...

What is virtual memory? How address mapping is done in cache memory? Elaborate your answer with examples.

Java programming, what are the phases of oo progarmming or java?

what are the phases of oo progarmming or java?

Courier company , disvange and advantege of providing intternet sservice to...

disvange and advantege of providing intternet sservice to customer

Image processing, Image Processing: This technology is quite advanced ...

Image Processing: This technology is quite advanced and devices are now available for routine scanning and storage of printed pages, graphics, etc., which can then be retrieve

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