CSC 225
ALGORITHMS AND DATA STRUCTURES I
ASSIGNMENT 1
1. Indicate for each pair of expressions (A,B) in the table below, whether A is O or Ω of B.
Your answer should be in the form of a “yes” or “no” in each box.
A B O Ω
(log n)
3 n
2n
2 + 4n 4n
2
n! 2
n
n
5 n
4
100 100000
n
2
(1.5)n
2. Order the following list of functions by the big-Oh notation. All logarithms are to the base
2.
6n log n, log log n, 2
100
, 2
2
n
, 3n
0.5
, 4
log n
,(log n)
2
, n3
,
√
log n, 4
n
3. Solve Problem 1.4.6 on Page 208 in the textbook. It asks you to give the order of growth
(as a function of N) of the running times for three code fragments.
4. Prove by Induction:
Xn
i=1
(2i − 1) = n
2 ∀n ≥ 1
5. Prove by Induction:
Xn
i=1
1
i(i + 1) =
n
n + 1
∀n ≥ 1
6. An Array A contains n − 1 unique integers in the range [0, n − 1]. That is, there is one
number in this range that is not in A. Describe in pseudo-code an O(n)-time algorithm for
finding that number. You are only allowed to use O(log n) bits of additional space besides
the array A itself.
1
