I claim that if f = 0(g) and g = 0(h), then f = 0(h)? (a) What does it mean exac
ID: 3903524 • Letter: I
Question
I claim that if f = 0(g) and g = 0(h), then f = 0(h)? (a) What does it mean exactly, algebraically to say f O(g) (b) Prove my claim. Let H be an n x m matrix in which the entries of each row are sorted in increasing order from left to right and in which the entries in each column are sorted in increasing order from top to bottom. Give (first in words, then in pseudo-code) an efficient algorithm (better than O(n)) for finding the position of a given number x in H. State the big-O running time of your code.Explanation / Answer
Answer for 2.
pseudocode:
1) Find the middle element.
2) If middle element is same as key return.
3) If middle element is lesser than key then
….3a) search submatrix on lower side of middle element
….3b) Search submatrix on right hand side.of middle element
4) If middle element is greater than key then
….4a) search vertical submatrix on left side of middle element
….4b) search submatrix on right hand side.
Code:
Divide and Conquer method:
complexity =
O(n^1.58)
if n = m.
// Java program for implementation of divide and conquer algorithm
// to find a given key in a row-wise and column-wise sorted 2D array
class SearchInMatrix
{
public static void main(String[] args)
{
int[][] mat = new int[][] { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
int rowcount = 4,colCount=4,key=50;
for (int i=0; i<rowcount; i++)
for (int j=0; j<colCount; j++)
search(mat, 0, rowcount-1, 0, colCount-1, mat[i][j]);
}
// A divide and conquer method to search a given key in mat[]
// in rows from fromRow to toRow and columns from fromCol to
// toCol
public static void search(int[][] mat, int fromRow, int toRow,
int fromCol, int toCol, int key)
{
// Find middle and compare with middle
int i = fromRow + (toRow-fromRow )/2;
int j = fromCol + (toCol-fromCol )/2;
if (mat[i][j] == key) // If key is present at middle
System.out.println("Found "+ key + " at "+ i +
" " + j);
else
{
// right-up quarter of matrix is searched in all cases.
// Provided it is different from current call
if (i!=toRow || j!=fromCol)
search(mat,fromRow,i,j,toCol,key);
// Special case for iteration with 1*2 matrix
// mat[i][j] and mat[i][j+1] are only two elements.
// So just check second element
if (fromRow == toRow && fromCol + 1 == toCol)
if (mat[fromRow][toCol] == key)
System.out.println("Found "+ key+ " at "+
fromRow + " " + toCol);
// If middle key is lesser then search lower horizontal
// matrix and right hand side matrix
if (mat[i][j] < key)
{
// search lower horizontal if such matrix exists
if (i+1<=toRow)
search(mat, i+1, toRow, fromCol, toCol, key);
}
// If middle key is greater then search left vertical
// matrix and right hand side matrix
else
{
// search left vertical if such matrix exists
if (j-1>=fromCol)
search(mat, fromRow, toRow, fromCol, j-1, key);
}
}
}
}
Code:
Divide and Conquer method:
complexity =
T(n) = 3T(n/2) + O(1)
O(n^1.58)
if n = m.
// Java program for implementation of divide and conquer algorithm
// to find a given key in a row-wise and column-wise sorted 2D array
class SearchInMatrix
{
public static void main(String[] args)
{
int[][] mat = new int[][] { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
int rowcount = 4,colCount=4,key=50;
for (int i=0; i<rowcount; i++)
for (int j=0; j<colCount; j++)
search(mat, 0, rowcount-1, 0, colCount-1, mat[i][j]);
}
// A divide and conquer method to search a given key in mat[]
// in rows from fromRow to toRow and columns from fromCol to
// toCol
public static void search(int[][] mat, int fromRow, int toRow,
int fromCol, int toCol, int key)
{
// Find middle and compare with middle
int i = fromRow + (toRow-fromRow )/2;
int j = fromCol + (toCol-fromCol )/2;
if (mat[i][j] == key) // If key is present at middle
System.out.println("Found "+ key + " at "+ i +
" " + j);
else
{
// right-up quarter of matrix is searched in all cases.
// Provided it is different from current call
if (i!=toRow || j!=fromCol)
search(mat,fromRow,i,j,toCol,key);
// Special case for iteration with 1*2 matrix
// mat[i][j] and mat[i][j+1] are only two elements.
// So just check second element
if (fromRow == toRow && fromCol + 1 == toCol)
if (mat[fromRow][toCol] == key)
System.out.println("Found "+ key+ " at "+
fromRow + " " + toCol);
// If middle key is lesser then search lower horizontal
// matrix and right hand side matrix
if (mat[i][j] < key)
{
// search lower horizontal if such matrix exists
if (i+1<=toRow)
search(mat, i+1, toRow, fromCol, toCol, key);
}
// If middle key is greater then search left vertical
// matrix and right hand side matrix
else
{
// search left vertical if such matrix exists
if (j-1>=fromCol)
search(mat, fromRow, toRow, fromCol, j-1, key);
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.