Trying to wrap my head around some basic and common algorithms.. my current understanding of the question is in bold.
( 1 ) Assuming we have a sorted array with n items: at most how many times will a binary search compare elements?
I keep seeing ' 0(log(n)) ' pop up as a general answer for this type of question but I do not understand why. Is there not a whole number that answers this question (i.e. 2 or 3?)
( 2 ) Assuming we have an array with n items: at most how many times will a linear search compare elements?
Again, same as above, but now ' 0(n) ' seems to be the general answer to this question. Again, I do not really understand the power behind this answer and question why there is not some whole number answer?
( 3 ) Can someone explain an example when a linear search would be better than a binary search?
From the information I have gathered, it generally seems like a binary search is a better option, if possible, because it is of it's quickness. I'm having trouble seeing when a linear search would be a better option.
regarding 1&2, an absolute number as an answer would've been possible if an absolute number was provided as the size of the input. since the question asks about an arbitrarily sized array (of length n) then answer is also given in these terms.
you can read more about big O notation for details, but basically O(n) & O(log n) mean order of n & order of log(n) respectively. i.e. if the input size is 100, for example, the number of compared elements using linear search will also be in the order of 100 while using a binary search would require comparing ~ log(100) elements.
as for 3, binary search requires the input to be sorted...