This is the leetcode problem #544 where compression of the list takes place. I'm looking help on calculating the time complexity of this below code.
class Solution {
public String findContestMatch(int n) {
List<String> list = new ArrayList<>();
int count = 1;
while(count <= n){
list.add(String.valueOf(count));
count++;
}
List<String> result = compress(list);
return result.get(0);
}
//"1,2,3,4,5,6,7,8"
//"(1,8),(2,7),(3,6),(4,5)"
//((1,8),(4,5)),((2,7),(3,6))
//(((1,8),(4,5)),((2,7),(3,6)))
public List<String> compress(List<String> list){
if(list.size() == 1){
return list;
}
int left=0, right = list.size()-1;
List<String> result = new ArrayList<>();
while(left < right){
result.add("("+list.get(left)+","+list.get(right)+")");
left++;
right--;
}
return compress(result);
}
}
From what I see is :
T(n) = n + T(n-1); n > 1
1 ; n = 1
Looks like O(n!) from the above recursion equation.