CODEWITHSUNDEEP
cbig-otime-complexity
SomeoneWithAQuestion
SomeoneWithAQuestion

Reputation: 345

Time complexity of a function in Big-O

I'm trying to find the time complexity of this function:

int bin_search(int a[], int n, int x); // Binary search on an array with size n.

int f(int a[], int n) {
    int i = 1, x = 1;
    while (i < n) {
        if (bin_search(a, i, x) >= 0) {
            return x;
        }
        i *= 2;
        x *= 2;
    }
    return 0;
}

The answer is (log n)^2. How come?
Best I could get is log n. First the i is 1, so the while will be run log n times.
At first interaction, when i=1, the binary search will have only one interaction because the array's size is 1(i). Then, when i=2, two interactions, and so on until it's log n interactions.
So the formula I thought would fit is this.
The summation is for the while and the inner equation is because for i=1 it's log(1), for i=2 it's log(2) and so on until it's log(n) at the last.

Where am I wrong?

Upvotes: 0

Views: 205

Answers (1)

chqrlie
chqrlie

Reputation: 144645

Each iteration performs a binary search on the first 2^i elements of the array.

You can compute the number of operations (comparisons):

log2(1) + log2(2) + log2(4) + ... + log2(2^m)

log(2^n) equals n, so this series simplifies into:

0 + 1 + 2 + ... + m

Where m is floor(log2(n)).

The series evaluates to m * (m + 1) / 2, replacing m we get

floor(log2(n)) * (floor(log2(n)) + 1) / 2

->  0.5 * floor(log2(n))^2 + 0.5 * floor(log2(n))

The first element dominates the second, hence the complexity is O(log(n)^2)

Upvotes: 3

Related Questions