What is the Big-O of this pseudo code? I need a proper explain also

Question

This is the pseudo code that i want to calculate time complexity ,i think it is a binary search algorithm but i fail when calculating the complexity because it is reducing logarithamic.

   USE variables half-array,found,middle element
   SET half-array=initial array;
   SET found=True;

 Boolean SearchArray(half-array)

   find middle element in half-array;
   Compare search key with middle element;
   IF middle element==search key THEN
           SET found=True;
   ELSE
        IF search key< middle element THEN
          SET half-array=lower half of initial array;
        ELSE
          SET half-array=upper half of initial array;


 SearchArray(half-array)

Are you only running the method once, or are you running it recursively? — obizues, Apr 26 '17 at 13:49
It looks like you are running this method recursively, and with each iteration you are reducing the number of elements being searched by half. This is going to be a logarithmic reduction, i.e. O(log n). — Rion Williams, Apr 26 '17 at 13:51
http://stackoverflow.com/questions/10369563/difference-between-on-and-ologn-which-is-better-and-what-exactly-is-olo Think of O(n) as a single enumeration on a List of size n. O(log n) would be when the algorithm is much more efficient and doesn't enumerate the entire List, but uses logic to find the answer quicker as in a binary search — Novaterata, Apr 26 '17 at 13:58
Possible duplicate of [how to calculate binary search complexity](http://stackoverflow.com/questions/8185079/how-to-calculate-binary-search-complexity) — xandermonkey, Apr 26 '17 at 13:58
It is `O(42)`. Why? Because `42` is the answer of all questions available in the universe. — Harmlezz, Apr 26 '17 at 13:59
Rote learning of answers one question at a time will not teach you. You need to purchase and study https://en.m.wikipedia.org/wiki/Introduction_to_Algorithms — Lew Bloch, Apr 26 '17 at 16:35

score 3 · Accepted Answer · edited May 23 '17 at 12:25

3

It looks like you are running this method recursively, and with each iteration you are reducing the number of elements being searched by half. This is going to be a logarithmic reduction, i.e. O(log n).

Since you are reducing your elements by half each time, you need to determine how many executions will be needed to reduce it to a single element, which this previous answer provides a proof or if you are a more visual person, you can use the following diagram from this response:

edited May 23 '17 at 12:25

Community

1
1

answered Apr 26 '17 at 13:56

Rion Williams

74,820
37
200
327

can i write the answer like this, log/ln N – kalsara Magamage Apr 26 '17 at 13:58
You would simply write it as `O(logN)`. Big O notation generally ignores any coefficients, so if there were any (e.g. `O(2N)` == `O(N)`). – Rion Williams Apr 26 '17 at 14:00
Nope, you would ignore any specifics regarding bases as well (e.g. `O(log2N)` == `O(logN)`). Exponents are really the only exception to this, as `O(N^2)` is very different from `O(N^3)`. – Rion Williams Apr 26 '17 at 14:09

score 0 · Answer 2 · answered Apr 26 '17 at 14:04

Yes,It is indeed a binary search algorithm.The reason why it is called a 'binary' search is because,if you would have noticed,after each iteration,your problem space is reduced by roughly half (I say roughly because of the floor function). So now,to find the complexity,we have to devise a recurrence relation,which we can use to determine the worst-case time complexity of binary-search.

Let T(n) denote the number of comparisons binary search does for n elements.In the worst case,no element is found.Also,to make our analysis easier,assume that n is a power of 2.

BINARY SEARCH:

When there is a single element,there is only one check,hence T(1) = 1.
It calculates the middle entry then compares it with our key.If it is equal to the key,it returns the index,otherwise it halves the range by updating upper and lower bounds such that n/2 elements are in the range.
We then check only one of the two halves,and this is done recursively until a single element is left.

Hence,we get the recurrence relation:

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

Using the Master Theorem,we get the time complexity to be T(n) ∈ Θ(log n)

Also refer : Master Theorem

score 0 · Answer 3 · answered Apr 26 '17 at 14:05

You are correct in saying that this algorithm is Binary Search (compare your pseudo code to the pseudo code on this Wikipedia page: Binary Search)

That being the case, this algorithm has a worst case time complexity of O(log n), where n is the number of elements in the given array. This is due to the fact that in every recursive call where you don't find the target element, you divide the array in half.

This reduction process is logarithmic because at the end of this algorithm, you will have reduced the list to a single element by dividing the number of elements that still need to be checked by 2 - the number of times you do that is roughly equivalent (see below) to the number of times you would have to multiply 2 by itself to obtain a number equal to the size of the given array.

*I say roughly above because the number of recursive calls made is always going to be an integral value, whereas the power you would have to raise 2 to will not be an integer if the size of the given list is not a power of two.

What is the Big-O of this pseudo code? I need a proper explain also

3 Answers3