Public Group

# how to find time complexity of this ..

This topic is 3029 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi ,
This program finds a number in a 2dimensional sorted matrix ..
but i can't figure out how to find its time complexity ,,
#include<iostream>using namespace std;void find_num(int a[][3] , int row,int col,int curr_row ,int curr_col,int to_find){if(curr_row >= row || curr_col < 0){cout<<"num not found";return;}  if(a[curr_row][curr_col] == to_find)  {     cout<<"num found at ::"<<curr_row<<":"<<curr_col;return;  }else{  if(a[curr_row][curr_col] > to_find)    {    find_num( a,4,3,curr_row,curr_col-1,to_find);  }else{find_num( a,4,3,curr_row+1,curr_col,to_find);}return;}}int main(){int a[4][3] = {{ 1, 2, 10} ,{3, 4, 23},{4, 5, 24} ,{6,7,27}};int to_find = 7;find_num(a,4,3,0,2,to_find);}

Can some1 help ?

[Edited by - Zahlman on August 29, 2010 2:49:28 AM]

##### Share on other sites
Use a [source][/source] tag, and fix the indentation, then I might take a look at it.

##### Share on other sites
guys ..
someone please say something

##### Share on other sites
The time complexity is O(1) as the data set size is hard coded and there is a fixed worst-case time.

Try make your implementation work on arbitrary data sets.

##### Share on other sites
oh ..
my mistake

now imagine array a as a[M][N] ..

now can u tell the complexity ??

##### Share on other sites
Lower bound: O(1)
Upper bound: O(M+N)
Asymptotic: O(n).

##### Share on other sites
You would however still have to fix the hard-coded values with its recursive calls before it's anything but O(1). Not to mention you'd need to change the function prototype.
"col" isn't actually used here either.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633704
• Total Posts
3013460
×