algorithm - Recurrence relation of number of comparisons in binary search -
i have doubt recurrence relation number of comparisons in binary search.
i read recurrence can written t(n) = t(n/2) + 1 in website http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/ln250_weiss/l14-recrel.htm
according me should t(n) = t(n/2) + 2, in worst case element might not present in array , end doing 2 comparisons in each pass.
please tell me whether right or wrong.
i think right.
imho, compare b
means know a=b
, a>b
or a<b
@ same time. say, 1 comparison may have 3 different results.
but programming languages. have use 2 comparisons.
if mid == x: found it! # 1st else if mid < x: search right # 2nd else: search left
you mean ==
, <
2 comparisons.
it not affect result though. because use big o notation represent complexity. matter of constant, o
don't care it.
according master theorem. either +1
or +2
result same complexity o(log n)
.
what want limit (big-o
), not mathematical equation precise result.
i think matters here 1
, 2
both constant time. can split ==
, >
machine instructions, , may greater 2
. or maybe programming languages or cpu utilize comparison, cost 1
comparison. not matter here when doing asymptotic analysis.
Comments
Post a Comment