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

Word processing (wp), Word Processing (WP): Word Processing is one of ...

Word Processing (WP): Word Processing is one of the most widespread application software types in use today. Developed as a successor to primitive text editors that were popul

Program planning (preparation of a flow chart), Program Planning (Preparati...

Program Planning (Preparation of a Flow Chart) A flow chart is a graphic method for indicating a proposed or actual solution to the problem. A flow chart shows the steps a comp

Editor and assembler, Editor and Assembler:   To write a program in...

Editor and Assembler:   To write a program in any of the programming languages requires an editor.  This is  a program that is used to create text files. While saving the p

Geometric mean - algorithm, The geometric mean is obtained by multiplying a...

The geometric mean is obtained by multiplying all the four numbers and taking the fourth root of the product. Let x 1 ,x 2 ,x 3  and x 4  be the given four numbers then geometric

Wcdma – fdd technology, WCDMA – FDD technology Multiple access technology i...

WCDMA – FDD technology Multiple access technology is wideband CDMA (WCDMA) All cells at same carrier frequency Spreading codes used to separate cells and users Signal bandwidth 3.8

Chat, Chat: The word chat in English language means - casual conversat...

Chat: The word chat in English language means - casual conversation. On Internet it means the same, except that you need to use text and your keyboard skills are tested. Earli

Telecommunication networks architecture, Telecommunication Networks Archite...

Telecommunication Networks Architecture is the manner in which the components of thenetwork are organized and integrated to provide telecommunication services to users ofthe netwo

Cryptography, Assume |s1|=|s2|=n and consider the functions defined, for an...

Assume |s1|=|s2|=n and consider the functions defined, for any s1 and s2, as: (a) G1(s1,s2)=s1 xor s2, (b) G2(s1,s2)=(s1, s2, s1 xor s2). We have that: A. G1 and G2 are pseudo-ra

Kids, how do you let kids learn on it

how do you let kids learn on it

Web browser, Web Browser:   A Web browser is software application that ...

Web Browser:   A Web browser is software application that enables you to find, retrieve, and display information available on the World Wide Web (WWW). Browser also allows you

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