递归函数中的时间复杂性,其中递归减少了大小

我必须估计Solve()的时间复杂度:

// Those methods and list<Element> Elements belongs to Solver class

void Solver::Solve()
{
    while(List is not empty)
        Recursive();
}

void Solver::Recursive(some parameters)
{

    Element WhatCanISolve = WhatCanISolve(some parameters); //O(n) in List size. When called directly from Solve() - will always return valid element. When called by recursion - it may or may not return element
    if(WhatCanISolve == null)
        return;

    //We reduce GLOBAL problem size by one.
    List.remove(Element); //This is list, and Element is pointed by iterator, so O(1)

    //Some simple O(1) operations


    //Now we call recursive function twice.
    Recursive(some other parameters 1);
    Recursive(some other parameters 2);
}

//This function performs search with given parameters
Element Solver::WhatCanISolve(some parameters)
{
    //Iterates through whole List, so O(n) in List size
    //Returns first element matching parameters
    //Returns single Element or null
}

我的第一个想法是应该在O(n^2)附近。

然后我想到

T(n) = n + 2T(n-1)

其(根据wolframalpha)扩展为:

O(2^n)

然而,我认为第二个想法是错误的,因为n在递归调用之间减少了。

我还用大数据集进行了一些基准测试。以下是结果:

N       t(N) in ms
10000   480
20000   1884
30000   4500
40000   8870
50000   15000
60000   27000
70000   44000
80000   81285
90000   128000
100000  204380
150000  754390