1. Choose the correct while loop statement from the following that finds the range where are the element being search is present (x is the element being searched in an array arr of size n)?
a) while (i < n && arr[i] <= x)
i = i*2;
b) while (i < n && arr[i] <= x)
i = i/2;
c) while (arr[i] <= x)
i = i/2;
d) while (i < n)
i = i*2;
Explanation: In exponential search we first find the range where the element being searched can be present before applying binary search. We do this by comparing the value of element under search with the array elements present at the positions 1,2,4,8….n.
2. What is the time complexity of exponential sort?
a) O(n)
b) O(2n)
c) O(n log n)
d) O(log n)
Explanation: In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range. This takes O(log n) time in the worst case.
3. What is the auxiliary space requirement of an exponential sort when used with iterative binary search?
a) O(n)
b) O(2n)
c) O(1)
d) O(log n)
Explanation: Exponential search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).
4. What is the auxiliary space requirement of the exponential sort when used with recursive binary search?
a) O(n)
b) O(2n)
c) O(1)
d) O(log n)
Explanation: Exponential search requires an auxiliary space of log n when used with recursive binary search. This space is required for the recursion call stack space.
5. Which of the following searching algorithm is fastest?
a) jump search
b) exponential search
c) linear search
d) all are equally fast
Explanation: Exponential search has the least time complexity (equal to log n) out of the given searching algorithms. This makes exponential search preferable in most cases.
6. In which of the following case jump search will be preferred over exponential search?
a) jumping backwards takes significantly more time than jumping forward
b) jumping forward takes significantly more time than jumping backwards
c) when the given array is very large in size
d) when the given array is very small in size
Explanation: Jump search only needs to jump backwards once, while an exponential search can jump backwards up to log n times. Thus jump search will be preferred if jumping backwards is expensive.
7. Best case of the exponential search will have time complexity of?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Explanation: Best case of the exponential search will be when the first element of the array is the element that is being searched. In this case, only one comparison will be required. Thus it will have a time complexity of O(1).
8. Jump search has a better time complexity than the exponential search.
a) True
b) False
Explanation: The worst case time complexity of jump search and exponential searches are O(n1/2) and O(log n) respectively. So exponential search is better in terms of time complexity.
9. Exponential search performs better than binary search when the element being searched is present near the starting point of the array.
a) True
b) False
Explanation: Exponential search first finds the range where binary search needs to be applied. So when the element is present near the starting point of the array then exponential search performs better than standard binary search.
10. Choose the incorrect statement about exponential search from the following.
a) Exponential search is an in place algorithm
b) Exponential search has a greater time complexity than binary search
c) Exponential search performs better than binary search when the element being searched is present near the starting point of the array
d) Jump search has a greater time complexity than an exponential search
Explanation: Time complexity of exponential search and binary search are the same. But exponential search performs better than binary search when the element being searched is present near the starting point of the array.
Design and Analysis of Algorithms
What's the Buzz About Exponential Search?
Imagine you're lost in a library, searching for that elusive book. Instead of starting from A and going to Z, you decide to be smart. You begin at A, then jump to B, then C, and so on. This smart approach? That's Exponential Search, my friend!
In the algorithmic kingdom, Exponential Search is the savvy detective that quickly narrows down possibilities, reducing search time and saving the day.
Breaking Down the Magic
Exponential Search follows a divide-and-conquer strategy. It divides the haystack and, with each hop, slashes the possibilities. It's like a game of hot and cold—getting warmer, colder, until voila! You've found your treasure!
Here's the secret sauce: Exponential Search is ideal for sorted arrays. It uses the power of two to jump ahead, ensuring an efficient exploration.
Why Does Exponential Search Rock?
1. Time Complexity Dance: Ever heard of logarithmic time complexity? That's Exponential Search showing off, boasting a time complexity of O(log n).
2. Memory Whisperer: It's memory efficient. No need for fancy data structures. A simple sorted array and Exponential Search can outshine others.
Crack the Code with Design and Analysis of Algorithms MCQ
Ready to flex your algorithmic muscles? Dive into Design and Analysis of Algorithms MCQs. Test your knowledge, learn, and conquer the algorithmic universe!
In a nutshell, Exponential Search is the algorithmic hero simplifying our quest for information. So, hop on the algorithmic rollercoaster and let Exponential Search guide you through the twists and turns of efficiency! Happy searching!