BEU B.Tech CSE 4th Semester (Course Code: 105403) DAA Unit-1 syllabus is:

1. Introduction

2. Characteristics of Algorithm

3. Analysis of Algorithm

4. Asymptotic Analysis of Complexity Bounds

5. Best Case Analysis

6. Average Case Analysis

7. Worst Case Analysis

8. Performance Measurement of Algorithm

9. Time and Space Trade-offs

10. Analysis of Recursive Algorithms

11. Recurrence Relations

12. Substitution Method

13. Recursion Tree Method

14. Master's Theorem

• Simple definition

• Important concept points

• Examples wherever needed

• Notes written for BEU semester exams

• No unnecessary topics

Introduction to Design and Analysis of Algorithms (DAA)

Design and Analysis of Algorithms (DAA) is the branch of computer science that studies how to design efficient algorithms and how to measure their performance in terms of time and memory (space) before implementing them.

DAA is the study of creating the best way to solve a problem and checking how fast and how efficiently that solution works.

Important Concept Points

1. What is DAA?

• DAA stands for Design and Analysis of Algorithms.

• It helps us create algorithms that solve problems correctly and efficiently.

• It compares different algorithms to find the best one.

2. Why do we study DAA?

DAA helps us:

• Solve problems faster.

• Reduce execution time.

• Reduce memory usage.

• Compare multiple algorithms for the same problem.

• Build software that performs well even for very large inputs.

3. Main Parts of DAA

DAA has two main parts:

Design

• Creating an algorithm to solve a problem.

Analysis

• Measuring how much time and memory the algorithm uses.

4. Goal of DAA

The main goal is to design algorithms that are:

• Correct

• Fast

• Memory-efficient

• Easy to understand

• Scalable for large amounts of data

5. What does DAA measure?

DAA mainly measures:

• Time Complexity – How long an algorithm takes to run.

• Space Complexity – How much memory an algorithm uses.

6. Real-life Examples

• Finding the shortest path in Google Maps.

• Sorting student marks.

• Searching a contact in a phone.

• Finding the fastest route for food delivery.

• Searching products on an e-commerce website.

7. Why is DAA important?

Without DAA:

• Programs become slow.

• Memory is wasted.

• Large data becomes difficult to process.

With DAA:

1. Programs run faster.

2. Less memory is used.

3. Large problems become manageable.

• DAA = Design + Analysis

• Design means creating an algorithm.

• Analysis means measuring its efficiency.

• Efficiency is measured using time and space.

• The main aim is to choose the most efficient algorithm for solving a problem.

Common Algorithm Design Techniques

Algorithm design techniques are different approaches used to develop efficient algorithms for solving various computational problems.

Searching

• Used to find a specific element in a collection of data.

• Examples: Linear Search, Binary Search.

Sorting

• Used to arrange data in ascending or descending order.

• Examples: Bubble Sort, Merge Sort, Quick Sort.

Divide and Conquer

• Divides a problem into smaller subproblems, solves them recursively, and combines the results.

• Examples: Merge Sort, Quick Sort, Binary Search.

Brute Force

• Solves a problem by checking all possible solutions.

• Simple to implement but usually less efficient.

Greedy Method

• Makes the best possible choice at each step to obtain an optimal solution.

• Examples: Huffman Coding, Dijkstra's Algorithm, Fractional Knapsack.

Dynamic Programming

• Solves complex problems by storing the solutions of overlapping subproblems and reusing them.

• Examples: Fibonacci Series, 0/1 Knapsack, Matrix Chain Multiplication.

Algorithm

An algorithm is a finite sequence of well-defined and unambiguous step-by-step instructions designed to solve a specific problem or perform a particular task. It accepts zero or more inputs, processes them according to the defined steps, and produces one or more outputs. An algorithm always terminates after a finite number of steps and provides the correct result for every valid input.

Important points

• An algorithm can be represented using pseudocode or a flowchart before writing the actual program.

• The same problem can have multiple algorithms, but they may differ in efficiency.

• An algorithm can be implemented in any programming language.

• A good algorithm should be easy to understand, test, and maintain.

• The performance of an algorithm is evaluated using time complexity and space complexity.

Example

Algorithm to find the sum of two numbers

1. Start

2. Read A and B

3. Calculate Sum = A + B

4. Display Sum

5. Stop

Characteristics of an Algorithm

1. Input

• An algorithm may accept zero or more input values.

• Input provides the data required to solve the problem.

• Input can be given by the user, a file, or another program.

2. Output

• An algorithm must produce at least one output.

• The output is the final result after processing the input.

• One algorithm can produce one or more outputs.

3. Definiteness

• Every step of an algorithm must be clear, precise, and unambiguous.

• Each instruction should have only one meaning.

• Ambiguous instructions may lead to incorrect results.

4. Finiteness

• An algorithm must terminate after a finite number of steps.

• It should always have a stopping condition.

• An algorithm that runs forever is not considered valid.

5. Effectiveness

• Every instruction should be simple and executable.

• Each step must be completed in a finite amount of time.

• Every step should contribute to solving the problem.

6. Generality

• An algorithm should solve all valid instances of a problem.

• It should work correctly for different input values.

• The same algorithm should be reusable for similar problems.

Analysis of Algorithm

Analysis of an algorithm is the process of evaluating an algorithm to determine the amount of time and memory (space) it requires to solve a problem. It helps compare different algorithms and choose the most efficient one without depending on a specific computer, programming language, or compiler.

It measures two things

• Time Complexity — How long (or how many operations) an algorithm takes as the input size n increases.

• Space Complexity — How much memory an algorithm uses as the input size n increases.

We analyze algorithms before coding because coding a wrong algorithm wastes time and resources. Analysis is always done as a function of input size n.

Why is algorithm analysis needed?

• It helps compare two or more algorithms for the same problem.

• It identifies the most efficient algorithm.

• It predicts the performance of an algorithm before implementation.

• It helps reduce execution time and memory usage.

• It is independent of hardware and programming language.

Types of algorithm analysis

A priori Analysis

• Performed before implementing the algorithm.

• Based on theoretical analysis.

• Estimates time and space complexity using mathematical techniques.

• Does not require program execution.

A posteriori Analysis

• Performed after implementing the algorithm.

• Measures actual execution time and memory usage.

• Depends on factors such as hardware, operating system, compiler, and input size.

• Requires the program to be executed.

Example

Suppose there are two algorithms to sort 1,000 numbers.

• Algorithm A takes approximately 2 seconds.

• Algorithm B takes approximately 8 seconds.

By analyzing both algorithms, we conclude that Algorithm A is more efficient because it requires less execution time.

Asymptotic Analysis of Complexity Bounds

Asymptotic analysis is a method of evaluating an algorithm's efficiency by studying how its time complexity or space complexity grows as the input size (n) becomes very large. It focuses on the growth rate of an algorithm rather than the exact execution time.

Why do we use asymptotic analysis?

1. To compare algorithms without executing them.

2. To analyze performance for very large input sizes.

3. To ignore factors like processor speed, compiler, and programming language.

4. To identify the most efficient algorithm for large-scale problems.

5. To express complexity using standard asymptotic notations.

Key points

• The input size is represented by n.

• It describes the growth rate of an algorithm, not the exact running time.

• Constant values and lower-order terms are ignored because they have little effect for large values of n.

• It can be used to analyze both time complexity and space complexity.

• Asymptotic analysis is also known as asymptotic complexity analysis.

Example

Consider two algorithms:

1. Algorithm A performs 100n + 50 operations.

2. Algorithm B performs 5n + 10 operations.

As the value of n becomes very large, the constants (100, 50, 5, and 10) become less significant. The dominant term is n, so both algorithms have linear growth, represented as O(n).

Asymptotic Notation

Asymptotic notation is a mathematical notation used to represent the growth rate of an algorithm's time or space complexity as the input size (n) approaches infinity. It helps compare algorithms based on their efficiency.

Why do we use asymptotic notation?

• To represent complexity in a standard form.

• To compare different algorithms.

• To ignore constants and lower-order terms.

• To describe the upper, lower, or exact bound of an algorithm.

Types of Asymptotic Notation

1. Big O (O) – Upper Bound

2. Big Omega (Ω) – Lower Bound

3. Big Theta (Θ) – Tight Bound

Big O Notation (O)

Big O notation represents the upper bound or worst-case growth of an algorithm. It describes the maximum amount of time or memory an algorithm may require as the input size (n) increases.

Key points

• Represents the upper bound of complexity.

• Commonly used to analyze the worst-case performance of an algorithm.

• Helps estimate the maximum resources an algorithm may require.

• Ignores constants and lower-order terms.

• It is the most widely used asymptotic notation.

Example

For the function:

T(n) = 3n² + 5n + 10

The highest-order term is n², so

T(n) = O(n²)

Big Omega Notation (Ω)

Big Omega notation represents the lower bound or best-case growth of an algorithm. It describes the minimum amount of time or memory an algorithm requires as the input size (n) increases.

Key points

• Represents the lower bound of complexity.

• Commonly used to analyze the best-case performance.

• Shows the minimum resources required by an algorithm.

• Ignores constants and lower-order terms.

• Indicates that the algorithm cannot perform better than this bound.

Example

For the function:

T(n) = 3n² + 5n + 10

The lowest asymptotically significant term is still n², so

T(n) = Ω(n²)

Big Theta Notation (Θ)

Big Theta notation represents the tight bound or exact growth rate of an algorithm. It is used when both the upper bound and lower bound of an algorithm are the same.

Key points

• Represents the exact asymptotic complexity.

• Indicates both the upper and lower bounds are equal.

• Gives the most accurate description of an algorithm's growth.

• Ignores constants and lower-order terms.

• Used when the exact order of growth is known.

Example

For the function:

T(n) = 3n² + 5n + 10

Both the upper and lower bounds are n², therefore

T(n) = Θ(n²)

1. Best Case Analysis

Best case analysis measures the minimum time an algorithm takes to execute for a given input size. It occurs when the input is in the most favorable condition for the algorithm.

• Represents the minimum number of operations performed.

• Occurs under the most favorable input conditions.

• Usually represented using Big Ω (Omega) notation.

• It is not commonly used for comparing algorithms because it assumes the ideal situation.

Example

In Linear Search, if the required element is the first element of the array, only one comparison is needed.

Time Complexity: Ω(1)

2. Average Case Analysis

Average case analysis measures the expected time an algorithm takes to execute for all possible inputs of the same size. It represents the algorithm's performance under normal conditions.

• Represents the average number of operations.

• Assumes all valid inputs are equally likely.

• Gives a more realistic estimate of performance.

• Finding average case complexity is often more difficult than best and worst case.

Example

In Linear Search, if the element is equally likely to appear at any position, on average about n/2 comparisons are required.

Time Complexity: O(n)

3. Worst Case Analysis

Worst case analysis measures the maximum time an algorithm takes to execute for a given input size. It occurs when the input is in the least favorable condition.

• Represents the maximum number of operations.

• Occurs under the most unfavorable input conditions.

• Usually represented using Big O (O) notation.

• Most commonly used to compare algorithms because it guarantees the maximum execution time.

Example

In Linear Search, if the required element is the last element or is not present in the array, all elements must be checked.

Time Complexity: O(n)

Difference Between Best, Average and Worst Case

Example (Linear Search)

Suppose the array is:

[10, 20, 30, 40, 50]

Search for 10

• Best Case: Element found at the first position → 1 comparison → Ω(1)

Search for 30

• Average Case: Element found around the middle → 3 comparisons → O(n)

Search for 60

• Worst Case: Element not found, so every element is checked → 5 comparisons → O(n)

Types of Time Complexity

Time complexity is classified into the following types based on how the execution time of an algorithm grows as the input size (n) increases.

1. Constant Time – O(1)

2. Logarithmic Time – O(log n)

3. Linear Time – O(n)

4. Linearithmic Time – O(n log n)

5. Quadratic Time – O(n²)

6. Cubic Time – O(n³)

7. Exponential Time – O(2ⁿ)

8. Factorial Time – O(n!)

Constant Time – O(1)

An algorithm has constant time complexity if its execution time remains the same regardless of the input size. Increasing the input size does not affect the running time, because the algorithm performs a fixed number of operations.

Example: Accessing an array element using its index.

Logarithmic Time – O(log n)

An algorithm has logarithmic time complexity when the input size is reduced by a fixed factor in each step. The running time increases very slowly even if the input size becomes very large, making it highly efficient.

Example: Binary Search.

Linear Time – O(n)

An algorithm has linear time complexity when its execution time increases directly in proportion to the input size. If the input size doubles, the number of operations also approximately doubles.

Example: Linear Search.

Linearithmic Time – O(n log n)

An algorithm has linearithmic time complexity when it combines linear processing with logarithmic division of the problem. It is more efficient than quadratic algorithms and is commonly used in efficient sorting techniques.

Example: Merge Sort, Heap Sort.

Quadratic Time – O(n²)

An algorithm has quadratic time complexity when its execution time is proportional to the square of the input size. It usually occurs when two nested loops process the same data, causing the number of operations to grow rapidly.

Example: Bubble Sort, Selection Sort.

Cubic Time – O(n³)

An algorithm has cubic time complexity when its execution time grows in proportion to the cube of the input size. It commonly appears in algorithms that use three nested loops and becomes inefficient for large inputs.

Example: Simple Matrix Multiplication.

Exponential Time – O(2ⁿ)

An algorithm has exponential time complexity when its execution time doubles with every increase in the input size. The running time grows extremely fast, making such algorithms impractical for large values of n.

Example: Recursive Fibonacci Algorithm.

Factorial Time – O(n!)

An algorithm has factorial time complexity when it generates or checks every possible arrangement of the input. Its running time increases faster than exponential time and is practical only for very small input sizes.

Example: Brute Force solution for the Traveling Salesman Problem.

Order of Time Complexities (Best to Worst)

Growth Rate

Growth rate is the rate at which the execution time or memory usage of an algorithm increases as the input size (n) increases. It is used to compare the efficiency of different algorithms for large input sizes.

Complexity is represented using asymptotic notations, such as Big O (O), Big Omega (Ω), and Big Theta (Θ).

Order of Growth Rate

The following table shows the common time complexities arranged from the fastest (best) to the slowest (worst).

Relationship Between Growth Rate and Asymptotic Notation

Time and Space Trade-offs

A time and space trade-off is a design principle in which an algorithm improves one resource by sacrificing the other.

In other words, an algorithm may use more memory to reduce execution time or more execution time to reduce memory usage.

Why is a trade-off needed?

• Computers have limited memory and processing power.

• Some applications require faster execution, while others require lower memory usage.

• The choice depends on the problem and available system resources.

Time–Memory Trade-off

An algorithm stores additional data in memory to reduce repeated computations, resulting in faster execution.

Example: Merge Sort uses extra memory (O(n)) but achieves better time complexity (O(n log n)).

Space–Time Trade-off

An algorithm saves memory by avoiding extra storage, but this increases the execution time.

Example: Bubble Sort uses only O(1) extra memory but has a slower time complexity of O(n²).

Comparison

Key Takeaway

There is no algorithm that is best in every situation. Some algorithms are optimized for speed, while others are optimized for memory usage. Choosing the right algorithm depends on the requirements of the application and the available system resources.

Difference Between Performance Measurement and Algorithm Analysis

Why is Algorithm Analysis preferred?

Algorithm analysis is preferred because it is machine-independent. The same algorithm may take different execution times on different computers due to variations in processor speed, memory, operating system, or compiler.

However, algorithm analysis provides the same theoretical complexity regardless of the machine, making it a reliable method for comparing algorithms.

Finding Time Complexity of an Algorithm

Finding time complexity is the process of determining how the execution time of an algorithm grows as the input size (n) increases. It is calculated by counting the number of basic operations performed by the algorithm instead of measuring the actual execution time.

Steps to Calculate Time Complexity

1. Identify all the blocks of the program.

2. Find the time complexity of each block.

3. Add the complexities of sequential blocks.

4. Multiply the complexities of nested loops.

5. For if-else statements, take the maximum complexity of the two branches.

6. Ignore constant values and lower-order terms.

7. Keep only the highest-order term.

Rules for Calculating Time Complexity

Declaration

Variable declarations require a fixed amount of time regardless of the input size. Therefore, their time complexity is O(1).

Example

int i;
int sum;

Time Complexity: O(1)

Initialization

Initializing variables is performed only once, so its time complexity is O(1).

Example

int i = 0;
int sum = 0;

Time Complexity: O(1)

Iterative Statements (Loops)

The time complexity of a loop depends on the number of iterations it executes. For nested loops, multiply the complexities of each loop.

Conditional Statements

For if-else statements, only one branch is executed at a time. Therefore, the time complexity is the maximum of the two branches.

Rules to Remember

1. Declaration → O(1)

2. Initialization → O(1)

3. Sequential statements → Add the complexities.

4. Nested loops → Multiply the complexities.

5. If-else statements → Take the maximum complexity.

6. Ignore constant values such as 5, 10, n/2, 3n.

7. Keep only the highest-order term.
   

Example 1: Simple Linear Loop

for(int i = 0; i < n; i++)
{
    cout << i;
}

Solution

The loop executes n times.

Time Complexity = O(n)

Example 2: Logarithmic Loop

for(int i = 1; i <= n; i = i * 2)
{
    cout << i;
}

Solution

The values of i are:

1 → 2 → 4 → 8 → 16 → ...

After k iterations,

2ᵏ = n

Taking logarithm on both sides,

k = log₂n

Therefore,

Time Complexity = O(log n)

Example 3: Nested Loops

for(int i = 0; i < n; i++)
{
    for(int j = 0; j < n; j++)
    {
        cout << i << j;
    }
}

Solution
Outer loop executes n times.
Inner loop executes n times for each iteration of the outer loop.

Total iterations:

n × n = n²

Time Complexity = O(n²)

Example 4: Three Nested Loops

for(int i = 0; i < n; i++)
{
    for(int j = 0; j < n; j++)
    {
        for(int k = 0; k < n; k++)
        {
            cout << i << j << k;
        }
    }
}

Solution
First loop executes n times.
Second loop executes n times.
Third loop executes n times.

Total iterations:

n × n × n = n³

Time Complexity = O(n³)

Example 5: If-Else Statement

if(condition)
{
    for(int i = 0; i < n; i++)
    {
        cout << i;
    }
}
else
{
    for(int j = 0; j < n * n; j++)
    {
        cout << j;
    }
}

Solution

• if block → O(n)

• else block → O(n²)
  

Take the maximum of the two branches:

max(O(n), O(n²)) = O(n²)

Time Complexity = O(n²)

Recurrence Relation

A recurrence relation is a mathematical equation that expresses the running time of a recursive algorithm in terms of the running time of its smaller subproblems. It helps analyze the time complexity of recursive algorithms.

Why do we use Recurrence Relations?

• To represent the time complexity of recursive algorithms.

• To determine the total running time of recursive calls.

• To analyze Divide and Conquer algorithms such as Merge Sort and Binary Search.

• To solve recursive algorithms using methods like Substitution, Recursion Tree, and Master's Theorem.

General Form of a Recurrence Relation

The general form of a recurrence relation is:

T(n) = aT(n/b) + f(n)

Where:

• T(n) → Time complexity for input size n.

• a → Number of recursive calls.

• n/b → Size of each subproblem.

• f(n) → Time spent outside the recursive calls (such as dividing, merging, or processing).

Example

For Merge Sort,

T(n) = 2T(n/2) + n

Here,

• 2 recursive calls are made.

• Each subproblem has size n/2.

• Merging takes O(n) time.

How to Write a Recurrence Relation

Step 1: Count the Recursive Calls

Count how many times the function calls itself.

Step 2: Find the Size of Each Subproblem

Determine how much the input size decreases in every recursive call.

Step 3: Calculate the Remaining Work

Find the work done outside the recursive calls, such as comparisons, merging, or arithmetic operations.

Step 4: Write the Equation

Combine the recursive calls and the remaining work into a recurrence relation.

Example 1: One Recursive Call

void fun(int n)
{
    if(n <= 1)
        return;

    fun(n / 2);
}

Solution

Step 1: Number of recursive calls = 1

Step 2: Size of subproblem = n/2

Step 3: No extra work is performed.

Therefore,

T(n) = T(n/2) + O(1)

Example 2: One Recursive Call with Linear Work

void fun(int n)
{
    if(n <= 1)
        return;

    for(int i = 0; i < n; i++)
        cout << i;

    fun(n / 2);
}

Solution

Step 1: Number of recursive calls = 1

Step 2: Size of subproblem = n/2

Step 3: The loop executes n times.

Therefore,

T(n) = T(n/2) + O(n)

Example 3: Two Recursive Calls

void fun(int n)
{
    if(n <= 1)
        return;

    fun(n / 2);
    fun(n / 2);
}

Solution

Step 1: Number of recursive calls = 2

Step 2: Size of each subproblem = n/2

Step 3: No extra work is performed.

Therefore,

T(n) = 2T(n/2) + O(1)

Example 4: Merge Sort

MergeSort(A, l, r)
{
    if(l < r)
    {
        mid = (l + r) / 2;

        MergeSort(left half);
        MergeSort(right half);

        Merge(left, right);
    }
}

Solution

Step 1: Recursive calls = 2

Step 2: Size of each subproblem = n/2

Step 3: Merging both halves takes O(n) time.

Therefore,

T(n) = 2T(n/2) + O(n)

Example 5: Binary Search

BinarySearch(A, low, high)
{
    mid = (low + high) / 2;

    if(key == A[mid])
        return mid;

    if(key < A[mid])
        BinarySearch(left half);
    else
        BinarySearch(right half);
}

Solution

Step 1: Only one recursive call is made.

Step 2: The search space becomes n/2.

Step 3: Finding the middle element requires constant time.

Therefore,

T(n) = T(n/2) + O(1)

Common Recurrence Relations

Important Note

A recurrence relation only represents the running time of a recursive algorithm. It does not give the final time complexity. To obtain the final complexity, the recurrence must be solved using one of the following methods:

1. Substitution Method

2. Recursion Tree Method

3. Master's Theorem

How to Form a Recurrence Relation

To write a recurrence relation, ask the following three questions for every recursive algorithm.

Question 1: How many recursive calls are made?

Count how many times the function calls itself.

fun(n/2);

Recursive calls = 1

fun(n/2);
fun(n/2);

Recursive calls = 2

fun(n-1);
fun(n-1);
fun(n-1);

Recursive calls = 3

Question 2: What is the size of each recursive call?

Look at the argument passed to the recursive function.

Question 3: How much work is done outside recursion?

Ignore the recursive calls and observe the remaining code.

fun(n/2);

Nothing else is executed.

Extra work = O(1)

for(int i=0;i<n;i++)
    cout<<i;

fun(n/2);

The loop executes n times.

Extra work = O(n)

for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
        cout<<i<<j;
}

fun(n/2);

Two nested loops.

Extra work = O(n²)

Formula

Now simply combine all three answers.

T(n)
=
(Number of Recursive Calls)
×
T(Subproblem Size)
+
Extra Work

Now the examples become very easy.

Example 1

void fun(int n)
{
    if(n<=1)
        return;

    fun(n/2);
}

Step 1

How many recursive calls?

fun(n/2);

Only one.

So,

1 × T(?)

Step 2

What is the input of the recursive call?

fun(n/2)

Input size becomes n/2.

So,

1 × T(n/2)

Step 3

Any extra work?

No loop.

No calculation.

Only function call.

Extra work = O(1)

Final Answer

T(n)=T(n/2)+O(1)

Example 2

void fun(int n)
{
    if(n<=1)
        return;

    for(int i=0;i<n;i++)
        cout<<i;

    fun(n/2);
}

Step 1

Recursive calls?

Only one.

1 × T(?)

Step 2

Recursive input?

fun(n/2)

So,

T(n/2)

Step 3

Extra work?

for(int i=0;i<n;i++)

Loop executes n times.

Extra work = O(n)

Final Answer

T(n)=T(n/2)+O(n)

Example 3

void fun(int n)
{
    if(n<=1)
        return;

    fun(n/2);
    fun(n/2);
}

Step 1

How many recursive calls?

fun(n/2);
fun(n/2);

There are two recursive calls.

So,

2 × T(?)

Step 2

Input size?

Both receive

n/2

So,

2T(n/2)

Step 3

Extra work?

Nothing except recursive calls.

Extra work = O(1)

Final Answer

T(n)=2T(n/2)+O(1)

The total time to solve a problem of size n equals the time to solve two smaller problems of size n/2 plus some constant work done outside the recursive calls.

Recursion Tree Method

The Recursion Tree Method is a technique used to solve recurrence relations by representing the recursive calls in the form of a tree. The cost at each level of the tree is calculated, and the costs of all levels are added to obtain the total time complexity.

Steps of the Recursion Tree Method

1. Draw the recursion tree.

2. Calculate the cost of each level.

3. Observe the pattern.

4. Find the height of the tree.

5. If every level has the SAME cost

→ Multiply by height.

6. If every level has DIFFERENT costs

→ Add all level costs (Geometric Series).

7. Write the final time complexity.

Rule to remember

1. If every level has the same cost → Total Cost = Level Cost × Height.

2. If different levels have different costs → Add the costs of all levels (usually a geometric series).

Solve using the Recursion Tree Method

Master's Theorem

Master's Theorem is a method used to directly find the time complexity of recurrence relations of the form

without using the Substitution Method or the Recursion Tree Method. It is applicable only to divide-and-conquer recurrences of this standard form.

2. Standard Form

Every recurrence must first be written in the form

where

• a = Number of recursive calls

• b = Factor by which the input size is divided

• f(n) = Work done outside the recursive calls

Example

3. Steps to Apply Master's Theorem

Step 1

Write the recurrence in standard form.

Step 2

Identify

Step 3

Calculate

Step 4

Compare

with

Step 5

Choose the correct case of Master's Theorem.

4. Case 1

Condition

If

for some ,

then

Meaning

The recursive work is larger than the non-recursive work.

Example

Step 1

Step 2

Step 3

Compare

Hence, Case 1 applies.

Final Answer

5. Case 2

Condition

If

then

For most BEU questions, k = 0, so

Meaning

The recursive work and the non-recursive work are equal.

Example

Step 1

Step 2

Step 3

Compare

Hence, Case 2 applies.

Final Answer

6. Case 3

Condition

If

and the regularity condition is satisfied, then

Meaning

The non-recursive work is larger than the recursive work.

Example

Step 1

Step 2

Step 3

Compare

Hence, Case 3 applies.

Final Answer

7. Summary Table

8. Exam Shortcut

1. Write the recurrence in the form .

2. Find a, b, and f(n).

3. Calculate .

4. Compare with .

5. Select Case 1, Case 2, or Case 3.

6. Write the final time complexity.