How to find average time complexity of backtracking algorithm?

Question

Problem is to decide if it is possible to partition a given array nums into k partitions. I've written a brute force backtracking algorithm. How do we analyse this algorithm to calculate average runtime (average over all possible inputs -input may be such that it ends up "back-tracking" multiple times or possibly none). I want to perform a rigorous analysis. Defition of the backtracking procedure, which is called from main() with arguments CanPartK(0,nums,visited,k,0,SUM) and visited[]=FALSE , is as follows:

 bool CanPartK(int start, vector<int>& nums, vector<bool>& visited, int k, int curr_sum, const int& SUM)
{
 // k*SUM = sum of elements of nums[]
 if(k==0) return true;
 if(curr_sum==SUM) return CanPartK(0, nums, visited, k-1, 0, SUM);
 
 for(int i=start; i<nums.size(); i++)
 { 
 if(!visited[i] && curr_sum+nums[i]<=SUM)
 {
 visited[i]=true;
 if(!CanPartK(i+1, nums, visited, k, curr_sum+nums[i], SUM)) 
 visited[i]=false; 
 else
 return true;
 }
 }
 
 return false;
}

Answer 1

First run your algorithm, count the iterations. Check how it varies with different inputs. Get some idea about the runtime.

Unless you have a good counter argument, backtracking tends to be exponential. However, backtracking will also tend to exclude huge numbers of cases if done right and the actual execution time can have huge variations 2^n or 20^n is a huge difference. That means exponential time algorithms can have huge improvements.