CODEWITHSUNDEEP
c++algorithmrecursiontime-complexity
peku33
peku33

Reputation: 3903

Time complexity in recursive function in which recursion reduces size

I have to estimate time complexity of 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
}

My first thought was that it should be somwhere around O(n^2).

Then I thought of

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

which (according to wolframalpha) expands to:

O(2^n)

However i think that the second idea is false, since n is reduced between recursive calls.

I also did some benchmarking with large sets. Here are the results:

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

Upvotes: 0

Views: 1078

Answers (2)

e0k
e0k

Reputation: 7161

Your algorithm is still O(2n), even though it reduces the problem size by one item each time. Your difference equation

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

does not account for the removal of an item at each step. But it only removes one item, so the equation should be T(n) = n + 2T(n-1) - 1. Following your example and

Saving the algebra by using WolframAlpha to solve this gives the solution T(n) = (c1 + 4) 2n-1 - n - 2 which is still O(2n). It removes one item, which is not a considerable amount given the other factors (especially the recursion).

A similar example that comes to mind is an n*n 2D matrix. Suppose you're only using it for a triangular matrix. Even though you remove one row to process for each column, iterating through every element still has complexity O(n2), which is the same as if all elements were used (i.e. a square matrix).

For further evidence, I present a plot of your own collected running time data:

Plot of your running time data

Upvotes: 2

Mikhail Maltsev
Mikhail Maltsev

Reputation: 1678

Presumably the time is quadratic. If WhatCanISolve returns nullptr, iff the list is empty, then all calls

Recursive(some other parameters 2);

will finish in O(1), because they are run with an empty list. This means, the correct formula is actually

T(n) = C*n + T(n-1)

This means, T(n)=O(n^2), which corresponds well to what we see on the plot.

Upvotes: 2

Related Questions