5 practice sets · Page 1 of 1
Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
True
False
Correct Answer: A — True
Explanation:
The worst case time complexity of Rabin Karp algorithm is O(m*n) but it has a linear average case time complexity. So Rabin Karp and naive pattern searching algorithm have the same worst case time complexity.
The naive pattern searching algorithm is an in place algorithm.
True
False
Correct Answer: A — True
Explanation:
The auxiliary space complexity required by naive pattern searching algorithm is O(1). So it qualifies as an in place algorithm.
What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
O(n + m)
O(m)
O(n)
O(m * n)
Correct Answer: B — O(m)
Explanation:
Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It an auxiliary space of O(m) for maintaining Z array.
What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
O(n + m)
O(m)
O(n)
O(m * n)
Correct Answer: A — O(n + m)
Explanation:
Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It has a time complexity of O(m + n) where m is the length of text and n is the length of the pattern.
What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
O(n)
O(n*m)
O(m)
O(log n)
Correct Answer: C — O(m)
Explanation:
KMP algorithm is an efficient pattern searching algorithm. It has a time complexity of O(m) where m is the length of text.
