请求分析给定递归函数的正确时间复杂度

函数代码 #

recursiveFunction(List<Input> list, int leftIndex, int rightIndex){

      if(rightIndex <= leftIndex){
          return new ArrayList<>(); 
      }

      if(rightIndex == leftIndex + 1){ // 注：原代码此处为赋值符号，应为判断相等的==
          return list;
      }

      midIndex = (leftIndex + rightIndex) / 2

      List<Input> leftHalf = list.sublist(left, mid)
      List<Input> rightHalf = list.sublist(mid, right)

      if(!someFunction(leftHalf)){
          recursiveFunction(list, leftIndex, midIndex);
      } else if(!someFunction(rightHalf)){
          recursiveFunction(list, midIndex, rightIndex);
      } else {
          leftMid = leftIndex + ((midIndex - leftIndex) / 2)
          rightMid = midIndex + ((rightIndex - midIndex) / 2)
          List l1 = leftHalf.sublist(left, leftMid);
          List l2 = leftHalf.sublist(leftMid, mid);
          List r1 = rightHalf.sublist(mid, rightMid);
          List r2 = rightHalf.sublist(rightMid, right);

          List set1 = new ArrayList<>(l1).addAll(new ArrayList<>(r1))
          List set2 = new ArrayList<>(l1).addAll(new ArrayList<>(r2))
          List set3 = new ArrayList<>(l2).addAll(new ArrayList<>(r1))
          List set4 = new ArrayList<>(l2).addAll(new ArrayList<>(r2))

          if(!someFunction(set1)){
              recursiveFunction(set1, 0, set1.size() - 1);
          } else if(!someFunction(set2)){
              recursiveFunction(set2, 0, set2.size() - 1);
          } if(!someFunction(set3)){
              recursiveFunction(set3, 0, set3.size() - 1);
          } else {
              recursiveFunction(set4, 0, set4.size() - 1);
          } 
      }
}

前提条件 #

• someFunction的时间开销与输入规模成正比：输入规模为n时耗时O(n)，规模为n/2时耗时O(n/2)
• 创建子列表、合并列表的时间远小于someFunction，可忽略不计

我的分析与疑问 #

1. 初步判断时间复杂度为O(n log n)，理由：每步输入规模减半，且每步最多触发一次递归调用；someFunction的开销随规模同步缩减，常数项在大O表示法中可忽略。
2. 已完成的工作：
   • 检查主定理，认为其不适用，因为递归外的f(n)并非多项式；
   • 通过递归树法得到表达式5T(n/2) + n/2，该形式类似归并排序，而归并排序的时间复杂度为O(n log n)。

请问该递归函数的正确时间复杂度是多少？

内容的提问来源于stack exchange，提问作者D159