recurance relation question

[knavely]

well im asked here to find a recurance for the worst case running time of this horrable "sorting algorythm"

anyway i found a recurance relation for the number of times the function is called

T(n) = T(n - floor(n/3) ) + 1

but im not sure where to go from here:

this is the algorythm:


void stoogeSort( int A[], int low, int high)
{
int third;

if( low + 1 ==high )
{
if( A[low ] > A[ high ] )
swap( A[ low ], A[ high ] );
}
else if (low + 1 < high )
{
third = (high - low + 1)/3;
stoogeSort(A, low, high-third);
stoogeSort(A, low+third, high);
stoogeSort(A, low, high-third);
}
}


:rolleyes:
any help would be sooooooo awsome.

[knavely]

sorry my recurance relation is:

T(n) = 3T(2n/3) + 1

since stoogeSort divides the problem into three problems 2 thirds the size of the original.