# Running Time of code??

• Time Complexity of following code is better than O(m+n) but still the actual running time is very bad. Why?

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null) return false;
int m = matrix.length;
if(m==0) return false;
int n = matrix[0].length;
if(n==0) return false;

return searchSubMatrix(matrix,0,m,0,n,target);
}

private boolean searchSubMatrix(int[][] matrix, int row_start, int row_end, int col_start, int col_end, int target) {
if(row_end==row_start+1)
return Arrays.binarySearch(matrix[row_start],col_start,col_end,target)>=0;
if(col_end==col_start+1){
int[] array = new int[row_end];
for (int i = row_start; i < row_end; i++) {
array[i] = matrix[i][col_start];
}
return Arrays.binarySearch(array,row_start,row_end,target)>=0;
}
int[] array1 = new int[row_end];
int[] array2 = new int[row_end];
for (int i = row_start; i < row_end; i++) {
array1[i] = matrix[i][0];
array2[i] = matrix[i][col_end-1];
}
int row_end_new = Arrays.binarySearch(array1,row_start,row_end,target);
if(row_end_new>=0) return true;
row_end_new = -(row_end_new+1);
if(row_end_new==0) return false;

int row_start_new = Arrays.binarySearch(array2,row_start,row_end,target);
if(row_start_new>=0) return true;
row_start_new = -(row_start_new+1);
if(row_start_new>=row_end) return false;

int col_end_new = Arrays.binarySearch(matrix[row_start],col_start,col_end,target);
if(col_end_new>=0) return true;
col_end_new = -(col_end_new+1);
if(col_end_new==0) return false;

int col_start_new = Arrays.binarySearch(matrix[row_end-1],col_start,col_end,target);
if(col_start_new>=0) return true;
col_start_new = -(col_start_new+1);
if(col_start_new>=col_end) return false;

return searchSubMatrix(matrix,row_start_new,row_end_new,col_start_new,col_end_new,target);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.