Description

To compute the complexity of
Complexity recursive algorithms it is necessary to
count the number of recursive calls.
There is basically two ways to do that. recursive algorithm. The other is a Algorithms be applied to all recursive algorithms.
of Recursive One is tricky, but can be applied to any
straightforward method, but it cannot
● Back-substitution method
○ Factorial
Counting the number of ○ Towers of Hanoi recursive calls ● Master method
○ Binary Search
○ Maximum Element in a array
CSC 6013 – Week 5
Back-Substitution Method
● Let’s see how it work in a practical example, the complexity of the factorial example.
Back-substitution can be used to solve linear equations.

Back-Substitution Method
● We can replace x by n-2:
● We can rewrite the recursive ○ T(n-2) = 1 + T((n-2)-1) relation replacing n: ○ T(n-2) = 1 + T(n-3)
○ T(x) = 1 + T(x-1) ● Replacing T(n-2) into the
● We can replace x by n-1: current recurrence relation: ○ T(n-1) = 1 + T((n-1)-1) ○ T(n) = 1 + 1 + T(n-2)
○ T(n-1) = 1 + T(n-2) ○ T(n) = 1 + 1 + 1 + T(n-3)
● Replacing T(n-1) into the original ● And we can keep performing recurrence relation: substitution backwards…
○ T(n) = 1 + T(n-1) ○ T(n) = 1 + 1 + 1 + 1 + T(n-4)
○ T(n) = 1 + 1 + T(n-2) ○ T(n) = 1 + 1 + 1 + 1 + 1 + T(n-5)
Back-substitution requires imagination.

Back-Substitution Method

●
● We can rewrite the recursive relation replacing n:
○ T(x) = 1 + 2T(x-1) ●
● We can replace x by n-1:
○ T(n-1) = 1 + 2T((n-1)-1)
○ T(n-1) = 1 + 2T(n-2)
● Replacing T(n-1) into the original
recurrence relation: ●
○ T(n) = 1 + 2T(n-1)
○ T(n) = 1 + 2(1 + 2T(n-2))
○ T(n) = 1 + 2 + 4T(n-2)
We can replace x by n-2:
○ T(n-2) = 1 + 2T((n-2)-1)
○ T(n-2) = 1 + 2T(n-3)
Replacing T(n-2) into the current recurrence relation:
○ T(n) = 1 + 2 + 4T(n-2)
○ T(n) = 1 + 2 + 4(1 + 2T(n-3))
○ T(n) = 1 + 2 + 4 + 8T(n-3) And we can keep performing substitution backwards…
○ T(n) = 1 + 2 + 4 + 8 + 16T(n-4)
○ T(n) = 1 + 2 + 4 + 8 + 16 + 32T(n-5)

Back-substitution requires imagination.
Back-Substitution Method

Substituting from n-k backwards we have:
○ T(n) = 1 + 2T(n-1)
○ T(n) = 1 + 2 + 4T(n-2)
○ T(n) = 1 + 2 + 4 + 8T(n-3)
○ T(n) = 1 + 2 + 4 + 8 + 16T(n-4)
Video: Solution for the recurrence relation of Tower of Hanoi.
○ T(n) = 1 + 2 + 4 + 8 + 16 + 32T(n-5)
…
The pattern is
T(n) = 20 + 21 + 22 + … + 2k-1 + 2kT(n-k)
Since we know T(0) = 0, which value of k gives n-k equal to 0?
● k = n
○ T(n) = 20 + 21 + … + 2n-1 + 2nT(n-n)
○ T(n) = 20 + 21 + … + 2n-1 + 2nT(0)
○ T(n) = 20 + 21 + … + 2n-1
○ T(n) = 20 + 21 + … + 2n-1 = 2n-1
O(2n)
There is basically two ways to do that.
Complexity One is tricky, but can be applied to
any recursive algorithm.
of Recursive The other is a straightforward
method, but it cannot be applied to Algorithms all recursive algorithms.
● Back-substitution method
To compute the complexity of recursive algorithms it is
necessary to count the number of recursive calls.
○ Factorial
○ Towers of Hanoi
● Master method
○ Binary Search
○ Maximum Element in a array
CSC 6013 – Week 5

Fifth Coding Project – P#5
1. Develop a Python program with a recursive algorithm to calculate the number of digits in the binary expansion/representation of a positive Integer n.
i. if n == 1, the answer is 1;
ii. if n > 1, the answer is 1 plus the number of digits in the binary representation of n//2.
b. Run your code for the instances: n = 256 and n = 750.
c. Create the recurrence relation and stopping condition for your algorithm, and compute the Big Oh complexity using either back substitution or the master method.
To both programs you have to submit the code (.py file) of your algorithm and a .pdf with the two suggested executions, the recurrence relation/stop condition, and the Big Oh development and result (show your work, not only the result).
Two algorithms to create, this is the first.
Fifth Coding Project – P#5
2. Develop a Python program with a recursive algorithm to calculate the sum of the squares of the positive Integers 12 + 22 + 32 + … + n2, given the value of n.
i. if n == 1, the answer is 1;
ii. if n > 1, the answer is n2 plus the sum of the squares up to (n-1)2.
b. Run your code for the instances: n = 12 and n = 20.
c. Create the recurrence relation and stopping condition for your algorithm, and compute the Big Oh complexity using either back substitution or the master method.
To this program you have to submit the code (.py file) and a .pdf as for the first program (show your work, not only the result).
Your task:
Fifth Quiz – Q#5
● The fifth quiz in this course covers the topics of Week 5;
● The quiz will be available this Friday, and it is composed by 10 questions;
● The quiz should be taken on Canvas (Module 5), and it is not a timed quiz:
○ You can take as long as you want to answer it (a quiz taken in less than one hour is usually a too short time);
● The quiz is open book, open notes, and you can even use any language Interpreter to answer it;
● Yet, the quiz is evaluated and you are allowed to submit it only once.
Your task: