CS472 Assignment 3: Practice with Big-Oh
CS472 - Analysis of Algorithms
January 27, 2015
The assignment contains a set of practice problems covering asymptotic measures
of efficiency and working with recurrence relations.
1. Show directly that $f(n)=n2+3n3 ∈ Θ(n3
). That is, use the definitions
of O and ? that f(n) is in both O(n
) and ?(n
2. Consider the following algorithm:
Algorithm 1: A Simple Nested Loop
j ← 1
while j <= n/2 do
i ← 1
while i <= j do
Output i and j;
What is the output when n = 6, n = 8 and n = 10? What is the time
complexity of this algorithm if we assume that n is divisible by 2?
3. A table game is played on a square grid of cells. Consider an algorithm
that starts with a single cell and on each of its n iterations add new
squares all around the outside of the cell being considered? The results
for n = 0, n = 1, and n = 2 can be found in Fig. 3.
(a) How many 1-by-1 cells are there after n iterations?
|$20.00||Computer Science, C Programming||lightsource||0 time(s)|