###### Algorithms

October 12, 2023###### GATE 2021 CS-Set-2

October 12, 2023# Algorithms

Question 35 |

The recurrence relation that arises in relation with the complexity of binary search is:

T(n) = T(n/2) + k, k a constant | |

T(n) = 2T(n/2) + k, k a constant | |

T(n) = T(n/2) + log n | |

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

Question 35 Explanation:

In binary search, search for the half of the list and constant time for comparing. So,

∴ T(n) = 2T(n/2) + k, k a constant

∴ T(n) = 2T(n/2) + k, k a constant

Correct Answer: A

Question 35 Explanation:

In binary search, search for the half of the list and constant time for comparing. So,

∴ T(n) = 2T(n/2) + k, k a constant

∴ T(n) = 2T(n/2) + k, k a constant

Subscribe

Login

0 Comments