HPSC PGT Subjective Questions
Q1. Explain the Binary Search algorithm. Describe its iterative and recursive
implementations with pseudocode and complexity analysis.
Ans: Introduction to Binary Search
Binary Search is an efficient algorithm used to find the position of a target element in a sorted
array. Unlike Linear Search, which checks each element sequentially, Binary Search divides
the search space in half with each step, reducing the number of comparisons significantly.
Working Principle
Step 1: Find the middle element of the array.
Step 2: If the middle element is the target, return its index.
Step 3: If the target is smaller than the middle element, search the left half.
Step 4: If the target is greater, search the right half.
Step 5: Repeat steps until the element is found or the search space is empty.
Binary Search only works on sorted data.
Iterative Implementation:
BinarySearch(arr, target):
low ← 0
high ← length(arr) - 1
while low ≤ high:
mid ← (low + high) // 2
if arr[mid] == target:
return mid
else if arr[mid] < target:
low ← mid + 1
else:
high ← mid - 1
return -1 // Target not found
1
HPSC PGT Subjective Questions
Recursive Implementation:
BinarySearchRecursive(arr, low, high, target):
if low > high:
return -1 // Target not found
mid ← (low + high) // 2
if arr[mid] == target:
return mid
else if arr[mid] > target:
return BinarySearchRecursive(arr, low, mid - 1, target)
else:
return BinarySearchRecursive(arr, mid + 1, high, target)
Time Complexity Analysis:
Let n be the number of elements in the array.
Best Case: O(1)
→ Target is found at the middle in the first comparison.
Average and Worst Case: O(log₂ n)
→ At each step, the search space is halved.
Space Complexity:
o Iterative: O(1)
o Recursive: O(log n) (due to function call stack)
2
HPSC PGT Subjective Questions
Q2. Compare Linear and Binary Search algorithms in terms of input requirements, time
complexity, and practical use cases.
Ans: Searching is a fundamental operation in computer science. Two commonly used
searching algorithms are Linear Search and Binary Search. Both are used to locate a target
element in a list or array, but they differ significantly in performance, applicability, and
efficiency.
Criteria Linear Search Binary Search
Input Requirement Works on unsorted or sorted Works only on sorted arrays
arrays
Algorithm Type Sequential search Divide-and-conquer
Approach Scans each element one by Repeatedly divides search
one range in half
Best-case Time O(1) (if element is at the start) O(1) (if element is at the
Complexity middle)
Average-case Time O(n) O(log n)
Complexity
Worst-case Time O(n) O(log n)
Complexity
Space Complexity O(1) O(1) for iterative, O(log n) for
recursive version
Number of Comparisons Up to n comparisons Up to log₂(n) comparisons
Implementation Simplicity Very easy Slightly more complex
Use Case Scenario Small or unsorted datasets Large and sorted datasets
Stability in Search Stable for all input types Requires sorted data, fails on
unsorted input
Example Application Searching in phone contacts Searching in dictionaries,
(unsorted) databases
3
HPSC PGT Subjective Questions
Practical Use Cases:
Linear Search:
o Useful when data is small and unsorted.
o Example: Searching a name in a short list of invitees.
o Suitable in embedded systems with low memory and where sorting isn’t
feasible.
Binary Search:
o Ideal for large datasets that are already sorted.
o Example: Looking up a word in a dictionary or a record in a sorted database.
4
HPSC PGT Subjective Questions
Q3: Derive the recurrence relation for Binary Search and solve it to determine its time
complexity.
Ans: Binary Search is an efficient algorithm to find an element in a sorted array by repeatedly
dividing the search interval in half. To analyze its efficiency, we derive and solve its
recurrence relation, which expresses how the algorithm's execution time depends on the
input size.
Understanding the Algorithm:
In Binary Search:
At each step, the array is divided into two halves.
One half is discarded, and the search continues in the other half.
The process continues until the target is found or the interval becomes empty.
At each recursive step, the array size reduces from n to n/2, performing a constant-time
comparison (O(1)) before proceeding to the next call.
Derivation of the Recurrence Relation:
Let:
T(n): Time complexity for searching an element in an array of size n.
Then:
In each recursive step, Binary Search does one comparison and continues on half the
array.
So the recurrence relation is:
T(n) = T(n/2) + c
Where:
T(n): Time taken for an input size n
T(n/2): Time taken for half of the array
c: Constant time for comparison and midpoint calculation
5
HPSC PGT Subjective Questions
Solving the Recurrence Relation:
We solve the recurrence using recursion tree or iteration method.
Method: Repeated Substitution
T(n)=T(n/2)+c
T(n/2)=T(n/4)+c
T(n/4)=T(n/8)+c
⋮
T(n)=T(n/2k)+kc
The base case is reached when n/2k = 1 ⇒ 2k = n ⇒ k = log2n
Substitute back:
T(n) = T(1) + c⋅log2n
T(n) = O(log n)
6
HPSC PGT Subjective Questions
Q4: Analyze the behavior of Linear Search when the key is not present in a list of 100
elements. How does this compare with Binary Search?
Ans: Searching is used to locate a target value in a data structure. When the key is not
present, the efficiency of the algorithm becomes even more important. Here, we analyze
how Linear Search and Binary Search behave in such a scenario, specifically for a list of 100
elements.
Behavior of Linear Search When Key Is Not Found:
Linear Search checks each element one-by-one from the beginning to the end.
For a list of 100 elements, if the key is not present, Linear Search will:
o Compare each of the 100 elements.
o Perform 100 comparisons in the worst case.
Time Complexity:
Worst-case: O(n) = O(100)
Best-case (if key is found early): O(1)
Result when key is absent:
Always worst-case time, since every element must be checked to confirm absence.
Behavior of Binary Search When Key Is Not found:
Binary Search divides the sorted list into halves repeatedly.
Even if the key is not present, Binary Search will:
o Continue halving the list until the search interval becomes empty.
o For 100 elements, it will take at most:
⌈log2(100)⌉=7 comparisons
Time Complexity:
Worst-case: O(logn) = O(log100) ≈ O(7)
The absence of the key does not increase the number of steps significantly.
7
HPSC PGT Subjective Questions
Aspect Linear Search Binary Search
Data Requirement Unsorted or sorted Must be sorted
Comparisons (Worst Case) 100 7
Performance on Key Not Found Very slow (checks all) Fast (halves search space)
Time Complexity O(n) = O(100) O(log n) ≈ O(7)
Scalability Poor for large n Excellent for large n
When the key is not present in a list:
Linear Search degrades to worst-case performance, scanning every element.
Binary Search maintains its logarithmic efficiency, even when the key is absent.
Hence, Binary Search is significantly more efficient — but only applicable if the data is sorted.
8
HPSC PGT Subjective Questions
Q5. Define and explain Big-O notation. Illustrate with a real-world algorithm example.
Ans: Big-O notation is a mathematical concept used in asymptotic analysis to describe the
upper bound of an algorithm's running time or space requirement in terms of input size nnn.
It provides a way to express how an algorithm's performance grows as the input size
increases, ignoring constants and lower-order terms.
Formal Definition:
Let f(n) and g(n) be non-negative functions.
We say that:
f(n)=O(g(n))
if there exist constants c > 0 and n0 such that for all n ≥ n0 , f(n) ≤ c⋅g(n)
Purpose of Big-O Notation:
Describes worst-case time or space complexity.
Helps compare the efficiency of algorithms independently of hardware.
Focuses on how algorithms scale with increasing input size.
Big-O Name Example
O(1) Constant Time Accessing an array element
O(log n) Logarithmic Time Binary Search
O(n) Linear Time Linear Search
O(n log n) Linearithmic Time Merge Sort
O(n2) Quadratic Time Bubble Sort
O(2n) Exponential Time Solving the Traveling Salesman
9
HPSC PGT Subjective Questions
Q6. Differentiate between Big-O, Omega, and Theta notations with proper mathematical
definitions and graphs.
Ans: Asymptotic notations are used to describe the growth behavior of an algorithm's time
or space complexity as input size increases. The three most commonly used notations are:
Big-O (O) – upper bound
Omega (Ω) – lower bound
Theta (Θ) – tight bound
Each has a distinct role in characterizing algorithm efficiency in best-case, average-case, and
worst-case analysis.
Big-O Notation (O) – Upper Bound:
Big-O gives the worst-case time complexity of an algorithm.
f(n)=O(g(n))
if there exist constants c > 0, n0 ≥ 0 such that
f(n) ≤ c⋅g(n), ∀n ≥ n0
The function f(n) does not grow faster than g(n) up to a constant multiple.
Example
If f(n)=3n+2, then f(n)=O(n).
Omega Notation (Ω) – Lower Bound:
Omega gives the best-case time complexity of an algorithm.
f(n)=Ω(g(n))
if there exist constants c > 0, n0 ≥ 0 such that
f(n) ≥ c⋅g(n), ∀n ≥ n0
The function f(n) grows at least as fast as g(n).
Example
If f(n)=3n+2, then f(n)=Ω(n)
10
HPSC PGT Subjective Questions
Theta Notation (Θ) – Tight Bound (4 marks)
Theta gives the average or exact growth rate (tight bound).
f(n) = Θ(g(n))
if there exist constants c1, c2 > 0, n0 ≥ 0 such that
c1⋅g(n) ≤ f(n) ≤ c2⋅g(n), ∀n ≥ n0
The function f(n) grows at the same rate as g(n), up to constant multiples.
If f(n) = 3n + 2, then f(n) = Θ(n)
Notation Meaning Usage Bounds
Big-O Upper bound (≤) Worst-case analysis f(n) ≤ c⋅g(n)
Omega Lower bound (≥) Best-case analysis f(n) ≥ c⋅g(n)
Theta Tight bound (=) Average/Exact growth c1⋅g(n) ≤ f(n) ≤ ⋅g(n)
11
HPSC PGT Subjective Questions
Q7. Explain best, worst, and average case complexities using a search algorithm as an
example.
Ans: In algorithm analysis, it's important to evaluate performance not just under ideal or
worst scenarios, but also on average. The best-case, worst-case, and average-case
complexities give a complete picture of how an algorithm behaves across different inputs.
These are typically expressed using asymptotic notations like Big-O, Omega, and Theta.
Case Definition
Best Case The minimum time or steps an algorithm takes under optimal input
conditions.
Worst Case The maximum time or steps the algorithm takes, usually under the least
favorable conditions.
Average Case The expected time the algorithm takes over all possible inputs of a given
size, assuming a uniform distribution of cases.
Example: Let’s use Linear Search to demonstrate these cases.
Linear Search Algorithm:
Scans each element in the list one by one until the target is found or the list ends.
Best Case (Ω(n))
Scenario: The target element is the first in the list.
Time Complexity:
T(n)=Ω(1)
Explanation: Only 1 comparison is needed.
Worst Case (O(n))
Scenario: The target element is the last in the list or not present.
Time Complexity:
T(n)=O(n)
Explanation: All n elements must be checked.
12
HPSC PGT Subjective Questions
Average Case (Θ(n))
Scenario: Assuming the target is equally likely to be anywhere or not present at all.
Time Complexity:
T(n)=Θ(n)
Explanation: On average, the algorithm checks about n/2 elements if the item is
present, and n elements if it is absent. This still simplifies to Θ(n).
Scenario Number of Comparisons Time Complexity
Best Case 1 Ω(1)
Average Case ~n/2 Θ(n)
Worst Case n O(n)
13
HPSC PGT Subjective Questions
Q8. Determine the asymptotic complexity (Big-O) for f(n) = 6n² + 3n + 1.
14
HPSC PGT Subjective Questions
Q9. Compare the growth of f(n) = n² and g(n) = 2ⁿ using tabular values for n = 1 to 10. Which
one grows faster, and why?
15
