0
$\begingroup$

How would you show that the worst-case run-time complexity for this algorithm is at least O(log n), where n is the length of the relevant list?

Suppose each time we go round the while-loop counts as a single step, and that all other operations can be completed in negligible time.

The algorithm is used for determining whether or not a value x is present in a sorted list of values, v = [v(1), . . . , v(n)].

  let m = 1;  
  while (1 <= m <= n) {  
    if (x == v(m)) {  
      exit with "x is present"  
    } else if (x < v(m)) {  
      let v = [v(1), ..., v(m-1)]; let n = m-1;  
    } else {  
      let v = [v(m+1), ..., v(n)]; let n = n - m;  
    };  
    let m = the integer part of (n+1)/2;
  };
  exit with "x is not present".

Thanks!

$\endgroup$
  • $\begingroup$ It's easier if you think of it in words. Check v(m). If x is there there, you're done. If x is too small, then check to the left of m. If x is too big, then check to the right of m. Then start checking at the middle of the list, so that the list is cut in half each time. In fact you could've started at the middle of the list to begin with. $\endgroup$ – Ian May 30 '17 at 16:03
  • $\begingroup$ Technically "at least $O(\log n)$" does not mean much. You might mean: "$\Theta(\log n)$" instead. $\endgroup$ – Did May 30 '17 at 16:04
  • $\begingroup$ @Ian, Thanks! Thinking of it that way made it so much easier. $\endgroup$ – Jack Williamson May 30 '17 at 16:17
1
$\begingroup$

suppose that $v=[1,2,\dots, n]$ and we have $x=n$. Then the while loop will be executed until $n$ becomes $1$, so this takes $\log_2 n$ steps (because $n$ is halved in each step).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.