I'm having a little trouble calculating the space-time complexity with a peak finding algorithm for matrices. I've already taken a class in algorithm analysis, but I'm afraid my professor didn't really explain anything that well in that class so I'm sort of stuck in figuring out my algorithm's complexity.
Regardless here's my code:
Code:
int matrix_peak(vector< vector<int> > m, int j)
{
int i;
/* 1D array brute force peak function,
modified to work with column iteration on
matrices. Time complexity is O(n)*/
if(m.size() == 1)
{
return recursive_peak_finder(m[0], 0, m[0].size());
}
for(i = 0; i < m.size() ; i++)
{
if(i > 0 && i < m.size()-1 &&
m[i][j] >= m[i+1][j] && m[i][j] >= m[i-1][j])
{
cout << m[i][j] << endl;
break;
}
else if(i == 0 && m[i][j] >= m[i+1][j])
{
cout << m[i][j] << endl;
break;
}
else if(i == m.size() - 1 && m[i][j] >= m[i-1][j])
{
cout << m[i][j] << endl;
break;
}
}
/* If peak is found in a middle column, it is returned
otherwise the function is called on a column which contains
a number greater than the greatest number in the current column. */
if(m[i][j] >= m[i][j+1] && m[i][j] >= m[i][j-1])
{
return m[i][j];
}
else if(m[i][j] < m[i][j+1])
{
return matrix_peak(m, j+1);
}
else if(m[i][j] < m[i][j-1])
{
return matrix_peak(m, j-1);
}
}
There's a function that's called in case the matrix has just one row, which is calling my peak finder for arrays, which is basically a binary search, meaning it has O(log n) time.
I'm not exactly sure how I'm supposed to write this I thought my algorithm could be determined with this:
T(nm, m/2) = O(n) + T(nm, m/2 -+1)
Can someone help me out, or point me to some tutorial that explains how to solve recurrences properly? What I'm not getting is how I can figure out which parameters T() is supposed to have.