CODEWITHSUNDEEP
javacomplexity-theory
user2214609
user2214609

Reputation: 4951

What is the Complexity of my function?

I want to find the Complexity of my function and i am not sure if it's O(n) or maybe something else

public static boolean find(int [][] mat, int x)
{
    int i = 1;
    int j = 0;
    int k = 0;
    int row = 0;
    int col = 0;
    int n = mat.length;
    while(i < n)//(see method discription)stage 1. loops over maxuim of n/2 times = O(n)
    {
        i = i * 2;
        if(x == mat[i-1][i-1])
            return true;
        else if (x < mat[i-1][i-1])
        {
            k = i / 2;
            row = col = i-1;
            break; //bigger value then x found, x is within the max and min values of the matrix. moving on to find a match.
        }
    }
    if (i > n)//x is bigger then max value of mat
        return false;

    for (j = k; j > 1; j = j / 2)//stage 2. locking on the right 2x2 matrix. runs k times. k<n O(n)
    {
        if(x == mat[row-j][col] || x == mat[row][col-j])
            return true;
        else if(x < mat[row-j][col])
            row = row - j;
        else if (x < mat[row][col-j])
            col = col - j;
    }
    //checking if x is within this 2x2 matrix
    if(x == mat[row][col-1])
        return true;
    else if(x == mat[row-1][col])
        return true;
    else if(x == mat[row-1][col-1])
        return true;
    else
        return false;
}

Upvotes: 0

Views: 106

Answers (1)

Ervadac
Ervadac

Reputation: 956

I would say O(log2(n)):

  1. first loop does log2(n) max iterations
  2. second loop depends on k < log2(n) and does max log2(k) operations

Upvotes: 1

Related Questions