CODEWITHSUNDEEP
algorithmmatrixdata-structuresanalysispseudocode
Rafat
Rafat

Reputation: 1

What is the worst-case runtime of this algorithm (in big-oh notation)?

The input is an N by N matrix of numbers. Each individual row is increasing from left to right. Each individual column is increasing from top to bottom. The example of a matrix is given below with N = 3.

3   4   5
4   5   8
6   7   9

The following is the basic naive algorithm (in pseudocode) to search for an item in the matrix:

bool search2DMatrix( int a[][], int N)
{
       for(int i = 0; i < N; i++)
             for(int j < 0; j < N; j++)
                   if ( item == a[i][j])
                             return true; 
        return false //if not found
}

Find an O(N) worst-case algorithm that finds if a number item is in the matrix. Write down the algorithm (in pseudocode) and show the analysis of the runtime of the algorithm.

I'm really struggling with trying to understand this and looking online isn't producing any helpful vidoes or resources. Would someone who knows algorithm analysis be able to help me through this problem? I'm taking a data structures class and the professor only posts 2 year old videos and ignores questions. Thank you in advance!

I have made this pseudocode but I don't think this is what the question is asking for.

  1. Start from the top-right corner of the matrix
  2. Now I need to initialize two variables
    • row with the value 0 is for the top row
    • column with the value N-1 is for the right column
  3. When row is less than or equal to N-1 and column is greater than or equal to 0 then repeat the steps 4, 5, and 6
  4. Compare the value at the current position matrix[row][column] with the target value X
    • If they are equal then return true because X exists in the matrix
    • If the value at the current position is greater than X move to the left column by descending column
    • If the value at the current position is less than I move to the next row by ascending row
  5. If I have exhausted all possible positions and haven't found X return false

Upvotes: -1

Views: 79

Answers (1)

trincot
trincot

Reputation: 351031

The trick to make it O(N) is to not start in the top-left cell of the matrix, but in the bottom-left cell of the matrix. At that position you are in the middle of an ordered sequence of 2N-1 items that run from (0, 0) to (n-1, 0) further to (n-1, n-1).

Now if the current cell has a value that is greater than the target value, then you know that all values at the right of the current cell are no longer relevant: we can move up one row (to row n-2). If at some point the value is less than what we look for, we can discard the column we are in, and move to column 1. And so we narrow down to the target cell.

Here is how that looks in code (I'd expect that you should pass item as an argument):

bool search2DMatrix(int a[][], int N, int item) {
    int r = N - 1;
    int c = 0;
    while (r >= 0 && c < N) {
        if (a[r][c] == item) return true;
        if (a[r][c]  > item) r--;
        else                 c++;
    }
    return false;
}

This way your loop will make at the most 2N-1 iterations, with at the most 2N evaluations of the loop condition.

Upvotes: 2

Related Questions