Register

GATE Data Science and Artificial Intelligence 2024 | Sample Paper | Question: 23

• edited by
2,077 views
0 0 votes

Which of the following correctly describes the recurrence relation for the standard binary search algorithm on a sorted array of $\mathrm{n}$ numbers where $\mathrm{c}$ is a constant.

  1. $\mathrm{T}(\mathrm{n})=2 ^{*} \mathrm{~T}(\mathrm{n} / 2)+\mathrm{c}$
  2. $\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n} / 2)$
  3. $\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n}-1)+\mathrm{c}$
  4. $\mathrm{T}(\mathrm{n})=\mathrm{T}(\mathrm{n} / 2)+\mathrm{c}$
     

     

2 Answers

0 0 votes

The correct recurrence relation for the standard binary search algorithm on a sorted array of n numbers is:

T(n) = T(n/2) + c

Voting & Accepting an answer helps improve the community
← Previous · GATE Data Science an...Next → · GATE Data Science an...
← Previous in category · GATE Data Science an...Next in category → · GATE Data Science an...
Position:
Show:

Related questions

1 1 vote
2 2 answers
6.5k
6.5k views
admin asked Oct 21, 2023
6,492 views
GATE Data Science and Artificial Intelligence 2024 | Sample Paper | Question: 2
Given $3$ literals $\text{A, B}$, and $\text{C}$, how many models are there for the sentence $\text{A $\vee$ $\neg$ B $\vee$ C}$ ?
3 3 votes
2 2 answers
6.2k
6.2k views
admin asked Oct 21, 2023
6,216 views
GATE Data Science and Artificial Intelligence 2024 | Sample Paper | Question: 3
Which of the following first-order logic sentence matches closest with the sentence "All students are not equal"?$\forall x \exists y[\operatorname{student}(x) \wedge \op...
1 1 vote
1 1 answer
2.9k
2.9k views
admin asked Oct 21, 2023
2,863 views
GATE Data Science and Artificial Intelligence 2024 | Sample Paper | Question: 4
The mean of the observations of the first $50$ observations of a process is $12$. If the $51$ $\text{st}$ observation is $18$, then, the mean of the first $51$ observatio...
1 1 vote
6 6 answers
6.9k
6.9k views
admin asked Oct 21, 2023
6,879 views
GATE Data Science and Artificial Intelligence 2024 | Sample Paper | Question: 6
Which among the following may help to reduce overfitting demonstrated by a modelChange the loss function. Reduce model complexity.Increase the training data.Increase the ...