CODEWITHSUNDEEP
ctime-complexitybig-ocomplexity-theory
Suryansh Manav
Suryansh Manav

Reputation: 73

What should be the time complexity of the given function in terms of Big O?

int find_peak (int n, int A []) {
    int left, right, lmid, rmid;
    left = 0;
    right = n - 1;
    while (left + 3 <= right) {
        lmid = (2 * left + right) / 3;
        rmid = (left + 2 * right) / 3;
        if (A[lmid] <= A[rmid])
            left = lmid;
        else
            right = rmid;
    }
    int x = left;
    for (int i = left + 1; i <= right; i ++)
        if (A[i] > A[x])
            x = i;
    return A[x];
}

I was trying to solve this function for its BigO notation, but I am very confused about it. Is it O(log n) or something else? I can somewhat solve it in my head but I can't do it on properly.

Upvotes: 2

Views: 78

Answers (2)

Priyanka Nigam
Priyanka Nigam

Reputation: 14

The complexity of the above code should be O(log3n) i.e...logn base 3. because in the while loop the value of rmid always comes out as greater than lmid.So, for a given value of right i.e...n, the value of left will be reduced by a multiple of 1/3 at each iteration.

Upvotes: 0

Jack Lilhammers
Jack Lilhammers

Reputation: 1247

Yes, the loop is cut roughly in half at each iteration

lmid = (2 * left + right) / 3;
rmid = (left + 2 * right) / 3;
if (A[lmid] <= A[rmid])
    left = lmid;
else
    right = rmid;

To be precise it's log1.5(n), because the actual length right-left decreases only by 1/3, not halving the iterations. The complexity is still O(log(n))

You can try it here https://onlinegdb.com/rkI5gn3Xd

Thanks to chqrlie for prompting me to give a more detailed answer

Upvotes: 1

Related Questions