After reading this, you’ll never get stuck in finding the time complexity of recursive algorithm
Have you ever been stuck finding the complexity of a recursive algorithm?
Let’s do an assessment! For each correct answers give yourself +1 marks else 0. And remember you have to find the complexity in less than 10 seconds!
Challenge Accepted? Let’s Start!
and The Answers are ::
- θ(logn)
- θ(n)
- θ(n)
- θ(logn)
So, how did you performed! If you answered all the answers correctly then Congratulation ✨, but if not don’t worry you will be equipped with all the stuff that you should know to answer these type of questions within 5 seconds!
To start thinking about these problems, The first step for you is to write recurrence relation for the recursive algorithms! Lets see how to do that!!
As you can see first of all we have marked all the statements with time they will take to execute, except loops, functions every statement can run in constant time!
if fun(n) is taking T(n) time then definitely fun(n/2) will take T(n/2) time to execute.
So finally we got our recurrence relation:: T(n) = T(n/2) + C
Let’s see more examples if got more than one recursive function and loops inside our algorithm then how to find recurrence relation.
As you can see this function has so much inside it, it is having nested loops, 2 recursive functions. To find its recurrence algorithm we’ll go like we did earlier, First of all we’ll write how much time every statement will take and if there is nested loops then they will run for n*m times (if n-times first loop, m-times second loop)
As you can see the recurrence relation we got for above function is:
T(n) = 2T(n/2) + nlogn + C
Remember, if you ever got this type of relation in loops then they’ll run for exactly
floor(logmN) + 1 times
Now, try to find out the recurrence relation of the questions that I asked earlier! Also try to find the recurrence relation whenever you see recursive function!!
After finding the recurrence relation, Next thing we should know is Extended Masters Theorem!!
Now, these are all the cases that you have to remember in order to answer the complexities of recurrence relation! If you wanna know how they all are derived then there is proof, you can refer here!
Lets, apply this theorem on the question that I asked you earlier, you’ll realize how easy it can be to find complexities within seconds.
This is the Q-1 that I asked in this as you can see this is the example of Case 2.c!
Just put the values of the parameters and there you go you have find the Time Complexity!!
CONGRATULATION!!
This is the question-2, In this case also first of all we find the recurrence relation and by using all the parameter we have found which case it belongs and put the values of the required parameter to estimate the complexity!!
Similar, you can find the complexities of the remaining question!
But remember, we can’t predict the complexities of all the recursive algorithm by using this method suppose if we are having T(n) = T(n-1) + C or T(n) = T(n/2) + T(2n/3) + n. To solve these kind of recurrence relation where the recursive functions, we can go with Substitution method or Recursive tree method! All the above questions we predicted from master theorem, we can you also find those with these method but that we’ll be complicated to solve!
Thankyou so much ❤❤for reading this article till here! I hope I am able to add some value in your learning journey! Happy Learning! Will see you in future with future blogs!
