How does “Recursive Algorithm Complexity” calculate ? For this problem we can use “Master Theorem”. According to this theorem, recursive relation doesn’t solve who evaluates as asymptotic in O() notation.
What is the Master Theorem?
Basically we suppose to a ≥ 1 integer and b,c, d real numbers (b>1, c>0, d>0) then give to following relation for T monotone increase function
It evaluates as following structure :
Shortly we can express such as following structure
We can calculate T(n) function algorithm complexity such as following structure
I know i know it’s a headache but we have to learn for recursive algorithm calculation just a bit patience then everything will be okey :)
Now I am considering we must do some exercise for understand.
// Exercise - 1
What is the algorithm complexity ?
T(n) = T(n/2) + 3n^2 + 5n
Explanation :
a=1;b=2;c=2 and 1 < 4(a < b^c)
Answer : T(n) = O(n^2)
// Exercise - 2
What is the algorithm complexity ?
T(n) = 2T(n/4) + 3/4√n
Explanation:
a=2;b=4;c=1/2; 2=4^1/2
Answer: O(√n * logn)
I almost forgot there is a exception situation for polylogarithmic functions.
Now let’s continue exercises but exercise is about daily time coding practice who doesn’t contain any academic practice
// Exercise - 3
What is the algorithm complexity?
Factorial(n) {
if == 0
return 1
else
return n * Factorial(n-1)
}
Explanation :
For this situation, basically we have three basic statement "==" has complexity 1, "*" has complexity 1, "-" has complexity 1
T(n) = T(n-1) + 3(this structure contains ==, *, - so 3) if n > 0
T(0) = 1
T(n) = T(n-1) + 3
T(n) = T(n-2) + 6
T(n) = T(n-3) + 9
T(n) = T(n-K) + 3K
n-k = 0 => k=n
T(n) = T(0) + 3n
T(n) = 3n + 1
And finally result O(n)
I think we are done. We talked about Master theorem and exception situation then solve some exercise and finally daily time coding practice. I hope this story usefull for you. See you next week.
I used resources to create this story :
Teoriden Uygulamalara Algoritmalar — Prof. Dr. Vasif Nabiyev
Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People — Aditya Bhargava
Finally I used exercises of this videos