Search code examples
recursionbig-ocomplexity-theoryrecurrencedivide-and-conquer

Big O Notation analysis using recursion tree

A problem from: http://qpleple.com/divide-and-conquer/ Comparison of algorithms

You are product manager at Facebook and three engineers from your team come up with these three algorithms to detect fake Facebook accounts in the list of n=1 billion Facebook accounts.

Rakesh solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.

Chris solves problems of size n by recursively solving two subproblems of size n−1 and then combining the solutions in constant time.

Matus solves problems of size n by dividing them into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n²) time

So by using the Master Theorem I found out that:

  • Rakesh's algorithm has a running time of O(nlog₂(5))
  • Matus' algorithm has a running time of O(n2log(n))

Drawing out a recursive tree and using:
equation

Rasket's algorithm has:

 #levels = log₂(n) 
 #of nodes at level k = 5k
 overhead per node at level k = n/2k

But no matter how hard I try, I can't get the summation to equal O(nlog₂(5)), and the same goes for Matus's algorithm.

Also, is there a way to solve the running time for Chris' algorithm with the Master Theorem?

Solution

  • Applying 

    #levels = log₂(n)
#of nodes at level k = 5k
overhead per node at level k = n/2k

    to Equation

    You get (using the geometric formula)

    T(n) = Σk=0,...,log₂(n) 5k ⋅ n/2k
     = n ⋅ Σk=0,...,log₂(n) (5/2)k
     = n ⋅ (1 - (5/2)log₂(n)+1) / (1 - 5/2)
     = (n - n ⋅ (5/2) ⋅ 5log₂(n) / 2log₂(n)) / (1 - 5/2)
     = (n - n ⋅ (5/2) ⋅ 5log₂(n) / n) / (1 - 5/2)
     = (n - (5/2) ⋅ 5log₂(n)) / (1 - 5/2)
     = ((5/2) ⋅ 5log₂(n) - n) / (5/2 - 1)
     = ((5/2) ⋅ 5log₂(n) - n) / (3/2)
     = (5/3) ⋅ 5log₂(n) - (2/3) ⋅ n             ∈ Θ(5log₂(n))

    Now you only have to show 5log₂(n) = nlog₂(5), which can be done in about one line.

    The recurrence equation, I get for Chris, is 

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

    This is not solvable by using the master theorem, but you can just expand it to a sum and solve it:

    T(n) = 2⋅T(n-1) + Θ(1)
     = 2⋅(2⋅T(n-2)+ Θ(1)) + Θ(1)
     = 2²⋅T(n-2) + 2⋅Θ(1) + Θ(1)
     ...
     = 2n⋅T(1) + 2n-1⋅Θ(1) + ... + 2⋅Θ(1) + Θ(1)
     = 2n+1⋅Θ(1) - 1         ∈ Θ(2n)

    This holds for T(1) ∈ Θ(1).