CODEWITHSUNDEEP
javatimecomplexity-theory
Melvil
Melvil

Reputation: 11

Time complexity of if statement with log n comparison

trying to wrap my head around big O notation and time complexity, finding it hard to understand how if statements affect the time complexity.

In the function below, the operation inside the if statement will only run once, because it will only go inside the If operation when binarySearch returns true for the input.

But the if statement will go O(n) times, using binarySearch which is log n.

Is the time complexity here O(n) or O(n*logn)? would love to have an explanation of the correct answer, since i find it hard to understand how the log n comparison of the if statement affect the time complexity of the method.

public static boolean what2 (int [][] m, int val)
{
    for (int i = 0; i < m.length; i ++)
    {
        if (binarySearch(m, val, i))
        {
            return true;
        }
    }
    return false;

Upvotes: 1

Views: 219

Answers (1)

Sportalcraft
Sportalcraft

Reputation: 265

How much time does the loop run? r times - O(r) - the number of rows.

for each row, perform a binary search - O(logc) - c is the length of the row

we are looking for the worst-case, in the worst case we never stop by entering the if, so we will iterate over all the rows

so the total run time is O(r*log(c)) [r - num of rows, c - num of colums]

note: if r = c = n then the run time can be simplified as O(nlogn)

Upvotes: 1

Related Questions