Design and Analysis of Algorithms
Question 1: Pseudo Codes for Checking the Largest of
Three Numbers
1. Constant Time Complexity: O(1)
This approach directly checks all possibilities using conditional
statements.
Algorithm LargestOfThree(a, b, c)
if a >= b and a >= c then
return a
else if b >= a and b >= c then
return b
else
return c
Time & Space Complexity: O(1)
The number of comparisons is fixed (2 comparisons in this case),
regardless of the input size.
The algorithm only uses a few constant-sized variables (`a`, `b`, `c`).
Hence, the space complexity is O(1) because no extra memory is
required.
2. Linear Time Complexity: O(n)
This approach simulates a linear comparison, evaluating the numbers
one by one.
Algorithm LargestOfThree(a, b, c)
max = a
if b > max_value then
max = b
if c > max then
max = c
return max
Time & space Complexity: O(n)
Comparisons are made sequentially, so it scales linearly, treating the
number of comparisons (2 here) as proportional to the number of
inputs.
Although the comparisons are sequential, only one additional
variable (`max_value`) is used to store the largest value. So the space
complexity is O(1).
3. Logarithmic Time Complexity: O(log n)
This can be achieved using a divide-and-conquer approach, though
here the recursive calls reduce the comparisons logarithmically.
Algorithm LargestOfThree (a, b, c)
function find_max(x, y)
if x >= y then
return x
else
return y
return find_max(find_max(a, b), c)
Time & space Complexity: O(log n)
The recursive divide-and-conquer approach reduces the number of
comparisons logarithmically by halving the comparisons in each step.
The divide-and-conquer method uses recursive calls, which consume
stack space. The space complexity in general is O(log n) due to the
recursive depth, though in this case (with only 3 numbers), it may be
close to O(1).
Question 2: Pseudo Code for Adding Two 3x3 Matrices
This pseudo code adds two 3x3 matrices element by element.
Algorithm AddMatrices(matrixA, matrixB)
resultMatrix = create_matrix(3, 3)
for i from 0 to 2 do
for j from 0 to 2 do
resultMatrix[i][j] = matrixA[i][j] + matrixB[i][j]
end for
end for
return resultMatrix
Time Complexity: O(1)
The time complexity is O(1) because the matrix size is constant, and
the number of operations (additions) is fixed, i.e., 9 operations (3x3
matrix).
Question 3: Pseudo Code for Prime Checking
This pseudo code checks whether a number is prime by iterating
from 2 to num-1.
Prime(num)
for i from 2 to num-1 do
if num mod i == 0 then
Print "Not Prime"
else
Print "Prime"
End
Time Complexity: O(n)
The time complexity is O(n) because in the worst case, the algorithm
performs (num - 2) iterations to check whether the number is prime
or not.
