TCYS133 Algorithm and Data
Structure
Tutorial
1. Define algorithm efficiency and explain why it is important in programming.
Algorithm efficiency refers to how effectively an algorithm uses resources (mainly time and
memory) as the size of input data increases. It measures how fast or slow an algorithm performs
relative to input size. It is important because different algorithms can solve the same problem
with vastly different performance. Efficient algorithms save time and computing power,
especially with large data sets.
2. Differentiate between linear loops and logarithmic loops with examples.
Linear Loop:
The loop variable increases or decreases by a constant value each iteration.
Example:
for (i = 0; i < 1000; i++)
// executes 1000 times
Efficiency: f(n) = n → O(n)
Logarithmic Loop:
The loop variable is multiplied or divided each iteration.
Example:
for (i = 1; i < 1000; i *= 2)
// executes log₂(1000) times
Efficiency: f(n) = log n → O(log n)
TCYS133 Algorithm and Data
Structure
3. What is meant by Big-O notation and why do we use it?
Big-O notation is a mathematical notation used in computer science to describe the worst-case
scenario or upper bound of an algorithm's time or space complexity. We use it to classify
algorithms based on how their runtime or memory usage grows as the input size (n) increases. It
allows us to compare the efficiency of different algorithms by focusing on the "order of growth"
and ignoring exact implementation details, constant factors, and lower-order terms. For example,
an O(n) algorithm will always be more scalable than an O(n2) algorithm for large inputs.
4. List and briefly explain four common time complexities in Big-O notation.
Time Complexity Description Example
O(1) Constant time – execution time does not depend Accessing an element in an
on input size. array.
O(log n) Logarithmic time – time grows slowly as data Binary search.
increases.
O(n) Linear time – time grows proportionally to input Scanning all elements in a
size. list.
O(n²) Quadratic time – time grows with the square of Nested loops, Bubble sort.
input size.
TCYS133 Algorithm and Data
Structure
5. Find the sum and multiplication of matrices.
SUM
1+7 4+3 8 7
5+11 -2+9 16 7
-3+3 4+(-8) 0 -4
6+(-2) 13+2 4 15
-7+(-14) 5+3 -21 8
4+(-3) 3+1 1 4
1+(-2) 6+4 4+(-1)
-1 10 3
-3+4 8+(-17) 9+(-5)
1 -9 4
-2+6 7+1 -1+8
487
TCYS133 Algorithm and Data
Structure
Multiplication
1x7+4x11 1x3+4x9 51 39
5x7+(-2)11 5x3+(-2)9 13 -3
-3(3)+4(-2) -3(-8)+4(2)
6(3)+13(-2) 6(-8)+13(2) -17 32
-8 -22
-7x(-14)+5x3 -7x3+5x1
83 -16
4x(-14)+3x(-3) 4x3+3x1
-65 15
1x(-2)+6x4+4x6 1x4+6x(-17)+4x1 1x(-1)+6x(-5)+4x8 -1 10 3
-3x(-2)+8x4+9x6 -3x4+8x(-17)+9x1 -3x(-1)+8x(-5)+9x8 1 -9 4
-2x(-2)+7x4+(-1)x6 -2x4+7x(-17)+(-1)x1 -2x(-1)+7x(-5)+(-1)x8 487
6. Define Big O notation and explain its significance in time complexity.
Big O notation expresses the upper bound of an algorithm’s growth rate—it shows the worst-
case performance as input size increases. It’s significant because it allows programmers to
predict scalability and choose the most efficient algorithm for large data sets. For example, O(n)
is much faster than O(n²) for large n
TCYS133 Algorithm and Data
Structure
7. Determine the big-O notation of the following:
4 2
i) 8 n +3 n +5
O(n⁴)
2
ii) n +50 n log log n+300
O(n2)
5 n 3
iii) 9 n + 4 +20 n
O(4n)
iv) Analyze the efficiency of the sorting algorithm in
(i). Polynomial time. This significantly is worse than O(n2) because it scales very poorly. For
example, if double input, the time could increase by a factor of 16(24). An algorithm with this
complexity would only be usable for very small input sizes. The significance O(n4 ) (O(nk)) are
in the "hours" category for n=10,000
(ii). Quadratic time. This significance generally considered inefficient for large datasets. For
example, if double the size of input (n) the time it takes will roughly quadruple (n2). For
n=10,000, the estimate time in "minutes".
(iii). Exponential Time. The algorithm is so slow that it becomes practically impossible to run for
even moderate input sizes. For example, if n=50, 450 is a number so large that no computer on
earth could finish the calculation in your lifetime.
The efficiency order:
O(n2)>O(n4)>O(4n)