How do you determine the Big-O notation of a while loop?
big-o
Solution
In each step, the range of values halves (roughly) - if you start with `right - left == 100`, then at the second step it will be 49, then 24, then 11 etc.
Assuming `n = right - left`, the complexity is O(log n). (It's dependent on the values of both right and left.)
Problem
Below is a binary search function. ``` int search(int a[], int v, int left, int right) { while (right >= left) { int m = (left + right)/2; if (v == a[m]) return m; if (v < a[m]) right = m - 1; else left = m + 1; } return -1; } ``` How do I determine the Big-O notation for this function? Is this search function O(n) since the while loop is dependent on the value of left?