0

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.

Chris
  • 112,704
  • 77
  • 249
  • 231

0 Answers0