CS2210b Data Structures and Algorithms Due: Thursday, January 20th

Assignment 1 (concept): Solutions

Note, throughout Exercises 1 to 4, n denotes the input size of a problem.

1. (10%) Rank the following functions by asymptotic growth rate in non-decreasing order:
( 32 )n , 264 − 1, n3 , 0.0001n2, 10000n, log n2 , 2log n , n log n, n2n , 21000 , n, n2 log n,
2n , log n, n100 , 4n , log n3 , nn , n3 log n

Answer:
264 − 1, 21000 , log n, log n2 , log n3 , n, 2log n , 10000n, n log n, 0.0001n2 , n2 log n,
n3 , n3 log n, n100 , ( 23 )n , 2n , n2n , 4n , nn .

Remark: In the above ranking, if a function f (n) preceeds another function g(n) then
f (n) ∈ O(g(n)) holds. Consequently, there are several valid answers. Indeed, several
of the above ranked functions f (n), g(n) satisfy f (n) ∈ Θ(g(n)), which implies that
both f (n) ∈ O(g(n)) and g(n) ∈ O(f (n)) hold.

Note:
(1) log n2 = 2 log n, log n3 = 3 log n
(2) Grouping these functions into the following classes can help to clarify their orders.
(a) Constant: 264 − 1, 21000
(b) Logarithmic: log n, log n2 , log n3
(c) Linear: n, 2log n , 10000n
(d) n log n
(e) Polynomial: 0.0001n2, n3 , n100
(f ) n2 log n
(g) n3 log n
(h) Exponential: ( 32 )n , 2n , n2n , 4n
(i) nn
Observe that the functions in the class (e) are not equivalent for the f (n) ∈
Θ(g(n)) relation. The same observation is true for the class (h).

2. (15%) Use the definition of Big-Oh to prove that 0.001n3 − 1000n2 log n − 100n + 5 is
O(n3 ).

Solution:
To show that 0.001n3 − 1000n2 log n − 100n + 5 is O(n3 ), we must find constants c > 0
and n0 ≥ 1 such that

0.001n3 − 1000n2 log n − 100n + 5 ≤ cn3 , ∀n ≥ n0 . (1)

1
 Inequality (1) is equivalent to the inequality below.
cn3 − 0.001n3 + 1000n2 log n + 100n − 5 ≥ 0 (2)

Inequality (2) must be true if the following inequality holds (where 1000n2 log n and
100n are dropped since they are positive, and −5 is multiplied by n3 ).
cn3 − 0.001n3 − 5n3 ≥ 0 (3)

Inequality (3) is equivalent to (c − 0.001 − 5)n3 ≥ 0, which is true ∀n ≥ n0 when

c = 5.001 and n0 = 1.
Now, we have found c = 5.001 and n0 = 1 such that 0.001n3 −1000n2 log n−100n+5 ≤
cn3 for all n ≥ n0 . Therefore, we have proved that 0.001n3 − 1000n2 log n − 100n + 5
is O(n3 ).
Remark:
The pair of c and n0 is not unique. For instance, when c = 1 and n0 = 2, Inequality
(1) always holds for n ≥ n0 .

3. (15%) Use the definition of Big-Oh to prove that n1+0.001 is not O(n).
Solution:
We prove that n1+0.001 is not O(n) by contradiction.
Suppose that n1+0.001 is O(n), which means that we can find c > 0 and n0 ≥ 1 such
that
n1+0.001 ≤ cn, ∀n ≥ n0 . (4)
By dividing both sides of the inequality of (4) by n (n ≥ 1) we obtain the following:
c ≥ n0.001 (5)

Inequality (5) can not be true since c must be a constant but n0.001 is unbounded. In
fact, as soon as n > e1000 log(c) we have c < n0.001 . This is a contradiction with the
assumption that we can find such a constant c. Therefore, n1+0.001 is not O(n).

4. (10%) Use the definition of Big-Oh to prove that if f (n) is O(g(n)), then af (n) is O(g(n)),
for any positive constant a.
Solution:
From the fact that f (n) is O(g(n)) we can find constants cf > 0 and n0f ≥ 1 such that
f (n) ≤ cf g(n), ∀n ≥ n0f . (6)
By multiplying both sides of the inequality of (7) by a (a > 0), we get
af (n) ≤ acf g(n), ∀n ≥ n0f . (7)
Let c = acf and n0 = n0f . We show that we can get constants c > 0 and n0 ≥ 1 such
that af (n) ≤ cg(n) for all n ≥ n0 . By the definition of Big-Oh, this proves that if
f (n) is O(g(n)), then af (n) is O(g(n)), for any positive constant a.

2
5. (25%) We want to know how many students are taking both CS2210 and CS2211 this
term. Let A and B be the class lists of CS2210 and CS2211. Each of A and B consists
of unique student IDs of the corresponding class. To keep it simple, we assume that
the two classes have the same number of students, denoted by n.

5.1 Write an algorithm in pseudocode to count the number of students who are taking
both CS2210 and CS2211 this term.
5.2 Compute the worst case running time T (n) of your algorithm with respect to the
class size n.
5.3 Give the best Big-Oh complexity characterization of T (n).

Solution 1:

5.1 Algorithm countCommon(A, B, n)

Input: Two integer arrays A and B with both size of n
Output: Number of common elements in A and B

e ← 0 //number of common elements

for i ← 0 to n − 1 do
for j ← 1 to n − 1 do
if B[j] = A[i] then
e=e+1
break
return e

5.2 The worst case occurs when there are no common elements in A and B. In such
case, every element in A needs to be compared with every element in B.
This algorithm involves a nested “for” loop. We analyze the inner-most “for”
loop first. In each iteration of the inner “for” loop, only a number of constant c
operations are performed (mainly one comparison). The number of iterations of
the inner “for” loop is n. Thus, the total number of operations performed in this
loop is cn. As for the outer (or first) “for” loop, the number of iterations is again
n. In each iteration of the outer “for” loop, it performs the work of the inner
loop. Therefore, the total work done by the outer “for” loop is n × cn = cn2 .
Consequently T (n) = cn2 + c′ where c′ is the number of operations for initializing
e and returning e at the end.

5.3 T (n) = cn2 + c′ is O(n2 ). (Proof is straightforward.)

3
 Solution 2:

5.1 Algorithm countCommon(A, B, n)

Input: Two integer arrays A and B with both size of n
Output: Number of common elements in A and B

Sort B by merge-sort or quick-sort

e ← 0 //number of common elements
for i ← 0 to n − 1 do
b ← binarySearch(A[i], B)
if b 6= null then
e=e+1
return e

5.2 The worst case happens when there are no common elements in A and B.
First, sorting the elements in B can be done in cn log n by either merge-sort or
quick-sort. Then, we can search in B for each element of A via binary-search,
which takes n × c′ log n = c′ n log n since the cost for each binary search is c′ log n.
In total T (n) = cn log n + c′ n log n.

5.3 T (n) = cn log n + c′ n log n is O(n log n).

Remark:
If both of the input arrays A and B are already sorted, one can achieve O(n) for
Algorithm countCommon by comparing the elements of A and B in sequence, akin to
the merge operation in merge-sort.

6. (25%) In the mathematical discipline of linear algebra, a matrix of the form

l1,1 0
 
 l2,1 l2,2 
..
 
L =  l3,1 l3,2
 . 
 (8)
 . . . .
 .. .. .. ..


ln,1 ln,2 . . . ln,n−1 ln,n

is called lower triangular matrix. For example, the following matrix is lower trian-
gular.  
1 0 0
2 8 0 (9)
4 9 7

Provided that li,i 6= 0 for 1 ≤ i ≤ n, a matrix equation in the form Lx = b, where

x = [x1 , . . . , xn ]T and b = [b1 , . . . , bn ]T , is very easy to solve by an iterative process

4
called forward substitution, reported as follows. The matrix equation Lx = b can
be written as a system of linear equations

l1,1 x1 = b1
l2,1 x1 + l2,2 x2 = b2
.. .. .. .. (10)
. . . .
ln,1 x1 + ln,2 x2 + · · · + ln,n xn = bn

Observe that the first equation (l1,1 x1 = b1 ) only involves x1 , and thus one can solve
for x1 directly. The second equation only involves x1 and x2 , and thus can be solved
once one substitutes in the already solved value for x1 . Continuing in this way, the
k-th equation only involves x1 , . . . , xk , and one can solve for xk using the previously
solved values for x1 , . . . , xk−1 . The resulting formulas are:
Pn−1
b1 b2 − l2,1 x1 bn − i=1 ln,i xi
x1 = , x2 = , · · · , xn = (11)
l1,1 l2,2 ln,n

Please refer to http://en.wikipedia.org/wiki/Triangular matrix for a general de-

scription about triangular matrices and the forward substitution process.
The following algorithm, ForwardSubstitution 1, is a straight-forward realization of
the forward substitution process reported above.

Algorithm ForwardSubstitution 1(L, b)

Input: 2-dimensional array L[1, . . . , n][1, . . . , n] encoding the triangular matrix in
Expression (1) such that L[i][j] = li,j ; An array b[1, . . . , n] where b[i] = bi .
Output: An array x[1, . . . , n] such that x[i] = xi as given in Expressions (11).

x[1] ← b[1]/L[1][1]
for i ← 2 to n do
v←0
for j ← 1 to i − 1 do
v ← v + L[i][j] × x[j]
x[i] ← (b[i] − v)/L[i][i]

6.1 Prove that the time complexity of Algorithm ForwardSubstitution 1 is O(n2).

Solution:
For this algorithm, there are no difference between best case and worst case.
It uses a nested “for” loop. We analyze the inner-most “for” loop first. In every
iteration of this loop a constant number c1 of operations is performed and the
loop is repeated for i − 1 times. Thus, the total number of operations performed
by this loop is c1 (i − 1). As for the first “for” loop, in every iteration it performs
a constant number of operations c2 to reset v to 0, c1 (i − 1) operations by the
second “for” block, and a constant number of operations c3 for calculating the

5
 value of xi . The first loop changes the values of i from 2 to n, thus the total
number of operations performed in this loop is
n
X
(c2 + c1 (i − 1) + c3 ) .
i=2

In total, the running time T (n) of Algorithm ForwardSubstitution 1 is

n
X
(c2 + c1 (i − 1) + c3 ) + c0 ,
i=2

where c0 is the number of operations for calculating x1 .

T (n) can be further simplified as follows.

T (n) = c2 (n − 1) + c1 (1 + 2 + 3 + · · · + n − 1) + c3 (n − 1) + c0
= c2 (n − 1) + c1 ( n(n+1)
2
− 1) + c3 (n − 1) + c0
c1 2 c1
= 2 n + ( 2 + c2 + c3 )n + c0 − c1 − c2 − c3

Therefore, Algorithm ForwardSubstitution 1 runs in O(n2 ).

6.2 (optional, 5% bonus) Can Algorithm ForwardSubstitution 1 be improved to

achieve O(n) time complexity? Adjust your reasoning regarding your answer.
Answer:
If none of the coefficients of the triangular matrix L is zero, then the cost for com-
puting x1 , x2 , . . . , xn lies in Θ(n2 ). Indeed, under this assumption, the account
(performed in the solution of the previous question) for the number of additions,
subtractions, multiplications and divisions is not over-estimated. In fact, this
amount of arithmetic operations is a sharp estimate. Therefore, under the hypoth-
esis that L[i][j] 6= 0 for 1 ≤ i ≤ n, 1 ≤ j ≤ i, Algorithm ForwardSubstitution 1
runs in Θ(n2 ) arithmetic operations.
Another argument is to observe that the number of coefficients in the triangular
matrix L is n(n+1)
2
. Therefore, we need Θ(n2 ) read operations for accessing all the
entries of the input data set.
Considering the amount of data that a given algorithm needs to read and write
is often used as an argument for proving that this algorithm requires at least a
given number of elementary operations.