Hrishikesh Rajan

How to find time complexity using the Master's Theorem

How to find time complexity using the Master's Theorem

Data Structures and Algorithms

Hrishikesh Rajan's photo
Hrishikesh Rajan
·

3 min read

In this article, we will learn the Master's Theorem from Daniel's story.

I so sad, I don't know what to do. (77).png One beautiful morning, Daniel was preparing for his dream job. Daniel is an engineering graduate. He is very hardworking, but he is also lazy. He is studying data structures and algorithms. He also has a friend named Therese, who is pretty smart and good at data structures. Let's see how Therese influences Daniel to learn the Master's Theorem

I so sad, I don't know what to do (26).png

I so sad, I don't know what to do. (45).png I so sad, I don't know what to do (1).png

Formula

I so sad, I don't know what to do. (47).png I so sad, I don't know what to do. (6).png

I so sad, I don't know what to do. (48).png I so sad, I don't know what to do (3).png I so sad, I don't know what to do. (17).png

Problem 1

math-20221021 (1).png STEP 1: I so sad, I don't know what to do. (22) (1).png I so sad, I don't know what to do. (21) (1).png STEP 2: I so sad, I don't know what to do (19).png

I so sad, I don't know what to do (6).png STEP 3:

I so sad, I don't know what to do (7).png I so sad, I don't know what to do. (8).png STEP 4: I so sad, I don't know what to do. (30) (1).png After substituting the value.

I so sad, I don't know what to do (8).png STEP 5: I so sad, I don't know what to do. (31) (1).png

I so sad, I don't know what to do. (43) (1).png I so sad, I don't know what to do. (10).png

Problem 2

math-20221021(2) (1).png Repeat the same steps that we did before.
STEP 1:

I so sad, I don't know what to do (23).png STEP 2:

I so sad, I don't know what to do (24).png STEP 3:

I so sad, I don't know what to do (11).png STEP 4:

I so sad, I don't know what to do. (74).png STEP 5:

I so sad, I don't know what to do (22).png Without deriving a lot of derivations, we can find the Time Complexity. But only recurrence relations involving fractional figures are suitable for Master's Theorem.

I so sad, I don't know what to do (17).png I so sad, I don't know what to do. (38) (1).png I so sad, I don't know what to do (21).png

data structuresdata structure and algorithms algorithms