COSC 1285/2123
COSC 1285/2123 Algorithms and Analysis
Workshop 2
Fundamentals of Algorithms Analysis
Tutorial Exercises
Objective
Students who complete this tutorial should:
� Understand basic data structures of arrays and linked lists.
� Understand the fundamentals of algorithm analysis.
� Have a sound understanding of the analysis framework used to evaluate the efficiency of algo-
rithms.
� Be familiar with asymptotic complexity.
1.4.2 If you have to search for an element in a list/collection of n numbers, how can you take
advantage of the fact that the list is known to be sorted? Give separate answers for:
a. lists represented as arrays.
b. lists represented as linked lists.
Answer:
1. Use binary search. We will learn about this soon, but we use a divide and conquer approach
to take advantage of the sortedness of the array.
2. When searching in a sorted linked list, stop as soon as an element greater than or equal to the
search key is encountered.
2.1.3 Consider a variation of sequential search that scans a list to return the number of occurrences
of a given search key in the list. Will its efficiency differ from the efficiency of classic sequential
search?
Answer: The algorithm will always make n key comparisons on every input of size n, whereas this
number vary between n and 1 for the classic version of sequential search.
2.1.9 Indicate whether the first function of each of the following pairs has a smaller, same or larger
order of growth (to within a constant multiple) than the second function.
a. 100n2 and 0.01n3.
b. log2(n) and loge(n).
c. (n− 1)! and n!.
Answer:
©2021 RMIT University 1
COSC 1285/2123
1. 100n2 (quadratic) has a lower order of growth than 0.01n3 (cubic).
2. Since changing a logarithm’s base can be done by the formula
loga(n) = loga(b) logb(n)
all logarithmic functions have the same order of growth to within a constant multiple.
3. (n− 1)! has a lower order of growth than n! = (n− 1)!n.
2.2.2 Use the informal definitions of O, Θ and Ω to determine whether the following assertions are
true or false.
a.
n(n+1)
2
∈ O(n3).
b.
n(n+1)
2
∈ O(n2).
c.
n(n+1)
2
∈ Θ(n3).
d.
n(n+1)
2
∈ Ω(n).
Answer: Using the guidelines about reducing the LHS function,
n(n+1)
2
≈ n2, hence has quadratic
growth. Therefore
1.
n(n+1)
2
∈ O(n3) is true.
2.
n(n+1)
2
∈ O(n2) is true.
3.
n(n+1)
2
∈ Θ(n3) is false.
4.
n(n+1)
2
∈ Ω(n) is true.
2.2.3 For each of the following functions, indicate the class Θ(g(n)) the function belongs to. (Use
the simplest g(n) possible in your answers). Prove your assertions.
a. (n2 + 1)10
b.
√
10n2 + 7n + 3
c. 2n log((n + 2)2) + (n + 2)2 log(n
2
)
d. 2n+1 + 3n−1
e. blog2(n)c (floor of log2(n))
Answer: First, simplify the functions given. Identify the dominant term, then construct the most
simple g(n) to have an exact bound.
a. (n2 + 1)10 = n20 + · · · ∈ Θ(n20).
b.
√
10n2 + 7n + 3 ≈
√
10n2 (we consider dominant term, as we want to analyse when n grows
larger).
√
10n2 =
√
10
√
n2 =
√
10 · n ∈ Θ(n).
©2021 RMIT University 2
COSC 1285/2123
c. (some log rules here are useful, log(n2) = 2 log(n) and log(n
b
) = log(n) − log(b). Using these
rules, 2n log((n + 2)2) + (n + 2)2 log(n
2
) = 4n log(n + 2) + (n + 2)2 log(n
2
) ≈ 4n log(n + 2) +
n2(log(n) − log(2)) ≈ n2 log(n) ∈ Θ(n2 log(n)) (as n2 log(n) had higher order of growth than
n log(n).
d. 2n+1 + 3n−1 = 21.2n + 3−13n ≈ 3n ∈ Θ(3n) (3−1 and 21 are constants).
e. blog2(n)c returns the floor of log2(n), e.g., blog2(3)c = b1.584c = 1. We know log2(n) ≥
blog2(n)c > log2(n) − 1. Given the upper (log2(n)) and lower (log2(n) − 1) bounds are ∈
Θ(log2(n)), then so is blog2(n)c ∈ Θ(log2(n)).
2.2.5 Order the following functions according to their order of growth (from the lowest to the
highest):
(n− 2)!, 5 log((n + 100)10), 22n, 0.0001n4 + 3n3 + 1, 3
√
n, 3n
Answer: First, simplify the functions given. Then use the list of functions in Table 2.2(book) to
simplify each of the functions given. Prove their final placement by computing appropriate limits
(get rid of constants etc).
1. (n− 2)! ∈ Θ((n− 2)!)
2. 5 log((n + 100)10) = 50 log(n + 100) ∈ Θ(log(n))
3. 22n = (22)n = 4n ∈ Θ(4n)
4. 0.0001n4 + 3n3 + 1 ∈ Θ(n4) (n4 is the dominant term)
5. 3
√
n = n
1
3 ∈ Θ(n
1
3 )
6. 3n ∈ Θ(3n)
The list of these functions ordered in increasing order of growth looks as follows:
5 log((n + 100)10), 3
√
n, 0.0001n4 + 3n3 + 1, 3n, 22n, (n− 2)!
©2021 RMIT University 3