ISRO CSE 2018 PYQ

Step-by-Step Explanation

When searching for an item that is not present in a hash table using linear probing, the algorithm starts at the computed hash value (starting bucket) and probes sequentially one by one until it encounters an empty slot, which terminates the search.
The number of comparisons required equals the number of occupied slots inspected plus 1 additional comparison for the empty slot that halts the search.
Let's calculate the number of comparisons needed for a non-present item starting at every possible bucket index (\(0\) to \(9\)):
• Start at Index 0: Checks index 0 (S7), index 1 (S1), index 2 (Empty) \(\rightarrow \) 3 comparisons
• Start at Index 1: Checks index 1 (S1), index 2 (Empty) \(\rightarrow \) 2 comparisons
• Start at Index 2: Checks index 2 (Empty) \(\rightarrow \) 1 comparison
• Start at Index 3: Checks index 3 (S4), index 4 (S2), index 5 (Empty) \(\rightarrow \) 3 comparisons
• Start at Index 4: Checks index 4 (S2), index 5 (Empty) \(\rightarrow \) 2 comparisons
• Start at Index 5: Checks index 5 (Empty) \(\rightarrow \) 1 comparison
• Start at Index 6: Checks index 6 (S5), index 7 (Empty) \(\rightarrow \) 2 comparisons
• Start at Index 7: Checks index 7 (Empty) \(\rightarrow \) 1 comparison
• Start at Index 8: Checks index 8 (S6), index 9 (S3), index 0 (S7), index 1 (S1), index 2 (Empty) \(\rightarrow \) 5 comparisons (Note: The search wraps around from index 9 back to 0)
• Start at Index 9: Checks index 9 (S3), index 0 (S7), index 1 (S1), index 2 (Empty) \(\rightarrow \) 4 comparisons

Step-by-Step Explanation

We are given the recurrence relation for \(n > 3\):
\(T(n)=T(n-1)+T(n-2)-T(n-3)\)
Let's substitute the options to find which relation produces a constant time complexity, \(O(1)\).

Testing Option A: \(T(1) = T(2) = T(3) = k\) (where \(k\) is a constant)

• For \(n = 4\):
\(T(4)=T(3)+T(2)-T(1)=k+k-k=k\)
• For \(n = 5\):
\(T(5)=T(4)+T(3)-T(2)=k+k-k=k\)
• For \(n = 6\):
\(T(6)=T(5)+T(4)-T(3)=k+k-k=k\)
By induction, \(T(n) = k\) for all \(n\). Since the running time stays completely fixed at a constant value \(k\) regardless of the size of \(n\), the order of the algorithm is constant (\(O(1)\)).

Why the other options are incorrect:

If we try any other relationship, the values will create a linear growth (\(O(n)\)). For example, testing Option B with values that satisfy \(T(1) + T(3) = 2 \cdot T(2)\) (such as \(T(1)=1, T(2)=2, T(3)=3\)):
• \(T(4) = 3 + 2 - 1 = 4\)
• \(T(5) = 4 + 3 - 2 = 5\)
This results in \(T(n) = n\), which means the time complexity is linear (\(O(n)\)) rather than constant.