Register

GO Classes DPP | PYTHON & DSA |BINARY SEARCH

174 views
1 1 vote

An array of $n$ elements is sorted. We want to search for an element using Binary Search. If we modified the algorithm to split the array into three equal parts instead of two (Ternary Search), what would be the recurrence relation for the time complexity?

  1. $T(n)=T(n / 3)+O(n)$
     
  2. $T(n)=T(n / 3)+O(1)$
     
  3. $T(n)=T(2 n / 3)+O(1)$
     
  4. $T(n)=3 T(n / 3)+O(1)$

1 Answer

0 0 votes
After two comparisons to determine which third the element is in, the search space is reduced to $n / 3$, with constant work per step.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | PYT...Next → · Nit Trichy mtech cse...
← Previous in category · GO Classes DPP | PYT...Next in category → · GO Classes DPP | PYT...
Position:
Show:

Related questions

1 1 vote
1 1 answer
162
162 views
GO Classes asked Feb 24
162 views
GO Classes DPP | PYTHON & DSA |GRAPH TRAVERSAL
Which of the following statements is TRUE regarding Breadth-First Search (BFS) and Depth-First Search (DFS) on an unweighted, connected graph?BFS finds the shortest path ...
2 2 votes
1 1 answer
159
159 views
GO Classes asked Feb 24
159 views
GO Classes DPP | PYTHON & DSA |HASHTABLE
Consider a hash table with $10$ slots using open addressing with linear probing. The hash function is $h(k)=k \text{(mod 10)}$. After inserting the keys $42,52,62$, and $...
1 1 vote
1 1 answer
156
156 views
GO Classes asked Feb 24
156 views
GO Classes DPP | PYTHON & DSA |QUICKSORT
During the execution of Quicksort on an array of $n$ distinct elements, if the pivot is always chosen such that it is the third smallest element in the current sub-array,...
0 0 votes
1 1 answer
180
180 views
GO Classes asked Feb 24
180 views
GO Classes DPP | PYTHON & DSA |CBT
A complete binary tree with $n$ nodes is represented in an array starting from index $1$. For a node located at index $i$, what is the index of its right child, and what ...