Algorithms, Basic Computer Science

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.
Posted Date: 9/11/2012 10:02:47 PM | Location : United States







Related Discussions:- Algorithms, Assignment Help, Ask Question on Algorithms, Get Answer, Expert's Help, Algorithms Discussions

Write discussion on Algorithms
Your posts are moderated
Related Questions
Given an operating system that supports a one – to –one relationship between user-level threads and kernel – level threads and allows one or more threads from a process to issue b

Question 1 Bring out the advantages of Linux Operating systems Question 2 Match the Symbols with their respective file types              Symbol               File N

how to measure marginal utility.?

Keystroke logger and Data-stealing: Keystroke loggers: This is a program, once installed on the system, which intercepts the keys when entering the password or the Credit Ca

Overview of a Computer System There are three major elements in every computer solution. They are:     Data     Hardware     Software Hardware + Softwa

In this assignment, you need to experiment with computer system measurements. Firstly, pick a platform to study. Any Unix-based system (such as a PC running some version of Linu

what is the sql command to List all the join conditions or join paths (pairwise) existing between tables.

draw the logic diagram of 2*4 decoder in only NOR gate .include enable inputs .


Define explicit, implicit and parametric representation and what are their advantages?