CODEWITHSUNDEEP
timebig-otime-complexitybinary-search-treebinary-search
Chantal
Chantal

Reputation: 111

Algorithm time complexity with binary search

I am trying to figure out what the time complexity of my algorithm is, I have algorithm with binary search, which is in general O(log n), I know. But I search between two constants, namely x=1 and x = 2^31 - 1 (size of integer). I think that in the worst case my time complexity is log2(2^31) = 31, so binary search takes 31 steps in the worst case. However every step in binary search I call a function, which has O(n) runtime (just one loop of the size of the input). Will my algorithm simply be of order O(31n)=O(n)?

The input of my algorithm: a key, two arrays a and b of size n.

In code it will look something like this:

    binarySearch(key, a, b)
    min = 0, max = 2^31 - 1
    mid = (min + max) / 2
    while (min<=max) { 
        x = function(mid, a, b); //this function has O(n)
        if (x==key) {
            return mid;
        } else if (x < key) { 
            min = mid + 1
        } else {
            max = mid - 1
        }
        mid = (min + max) / 2
    }
    return KEY_NOT_FOUND

I just want to be sure, please if you come with a time complexity (reduced ones) explain your answer.

Upvotes: 0

Views: 1231

Answers (1)

chiwangc
chiwangc

Reputation: 3577

Update

Yes, You are absolutely right.

In the worst case function() will be invoked 31 times, and each invocation requires time O(n), hence the running time of your algorithm is simply given by 31 * O(n) = O(n).


Solution for the original question where x = function(mid)

Your question is a bit fishy, the time complexity of your algorithm should be O(1).

One important point when we talk about the time complexity of an algorithm is that:

We always consider the time that the algorithm requires with respect to the size of it's input.

In the following snippet:

x = function(mid); //this function has O(n)

While function() may be a linear time function, but in your case, function() only takes input (mid) from the set {0, 1, ..., 230}, so in the worst case function() computes in time max{T(0), T(1), ..., T(230)} = T, which is a constant!

So in the worst case, your while loop will invoke function() 31 times, so in the worst case your algorithm runs in time 31 * T, which is a constant.

Note that the input of your algorithm is key, and the worst case running time of your algorithm is 31 * T, which is actually independent of the size of your input key! So the time complexity is O(1).

In your case, I don't think talking about time complexity in terms of big-O notation is appropriate. I would suggest you to talk about the numbers of computation steps required in the worst case.

Upvotes: 2

Related Questions