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

Mini computers and micro computers, Mini Computers and Micro Computers: ...

Mini Computers and Micro Computers: The mini computers are intermediate in power, and may function as small mainframe computers. They are often dedicated to a particular purpo

C, wap to print padovan string in c

wap to print padovan string in c

Batch processing, Batch Processing When the entire computer system is d...

Batch Processing When the entire computer system is dedicated to a single job, the system is said to be operating in Batch Processing mode. In this mode each program is run to

Explain the working of bus connection, Question 1 Explain the working of B...

Question 1 Explain the working of Bus connection Question 2 Write a note on: Robotics and Voice Recognition Question 3 Describe the construction of CD-ROM Question 4

How do you insert a symbol in a word document, Fundamentals of IT 1. Ho...

Fundamentals of IT 1. How do you insert a symbol in a Word document? 2. Explain absolute cell addressing? 3. Discuss Custom List? 4. Explain applications of Multimedia

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

Advantages and disadvantages of e-learning, Advantages and Disadvantages of...

Advantages and Disadvantages of E-Learning: Before we discuss about advantages and disadvantages of e-learning, you should know that e-learning is just another model for learn

Need a help, i am currently studying my computer science engineering 2nd yr...

i am currently studying my computer science engineering 2nd yr. i am unable to select what specification should i take please help me

Object oriented programming, Write a method called Grade that takes a numer...

Write a method called Grade that takes a numeric score and returns a letter grade. Use the rule that 90 to100 is an A, 80 to 89 a B, 60 to 79 is a C, 45 to 59 is a D, and less th

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