Q1] Solve the following recurrences using Master Theorem.

(i) T (n) = 16T(n/4) + n.

(ii) T (n) = T (2n/3) + 1

(iii) T(n) = 3T(n/4) + n log n

Ans: -
Q2] What are different asymptotic notations? Explain with neat graphs. If f(n) = sqrt (n) and g(n)=n
then prove that f(n) is Og(n).

Ans: -

There are three commonly used asymptotic notations:

1. Big O notation (O): It represents the upper bound or worst-case scenario of an algorithm's
time complexity. In simpler terms, it gives an upper limit on how much time an algorithm will take to
execute as the input size grows. For example, if an algorithm has a time complexity of O(n), it means
that the algorithm's runtime grows linearly with the input size or is at most proportional to the input
size.
2. Omega notation (Ω): It represents the lower bound or best-case scenario of an algorithm's
time complexity. It provides a lower limit on the growth rate of an algorithm as the input size
increases. For example, if an algorithm has a time complexity of Ω(n2), it means that the algorithm's
runtime grows at least quadratically with the input size.

3. Theta notation (Θ): It represents both the upper and lower bounds of an algorithm's time
complexity. It provides a tight bound on the growth rate of an algorithm. For example, if an algorithm
has a time complexity of Θ(n), it means that the algorithm's runtime grows linearly with the input
size, neither faster nor slower.
Q3] What are the different properties of algorithm? Which factors affect runtime of an algorithm?

Ans: -

Properties of Algorithms:

1. Correctness: An algorithm should produce the correct output for all possible inputs. It should
solve the problem it is designed for without any errors or inconsistencies.

2. Efficiency: Efficiency refers to the use of minimal resources, such as time and memory, to
execute an algorithm. Efficient algorithms optimize resource utilization and provide faster results.

3. Scalability: An algorithm should be able to handle larger input sizes without significant
performance degradation. It should have a reasonable time and space complexity that allows it to
scale well.

4. Robustness: Robust algorithms can handle unexpected inputs or edge cases without crashing
or producing incorrect results. They incorporate error handling and exception management
techniques.

Factors Affecting Runtime of an Algorithm:

The runtime of an algorithm is influenced by several factors:

- Input Size: As the size of the input increases, the runtime of the algorithm typically grows.
The relationship between the input size and the algorithm's runtime is often expressed using Big O
notation.

- Algorithm Design: The design choices made within an algorithm can significantly impact its
runtime. Different algorithms may have varying approaches to solving a problem, resulting in
different runtime characteristics.

- Computational Steps: The number and complexity of computational steps performed by an

algorithm affect its runtime. The more computations or iterations an algorithm requires, the longer
its runtime is likely to be.

- Data Structures and Operations: The choice of data structures and the operations performed
on them can affect runtime. Different data structures have varying time complexities for operations
such as insertion, deletion, search, and traversal, which impact the overall runtime of an algorithm.

- External Factors: The runtime of an algorithm can also be influenced by external factors such
as hardware capabilities, system load, and input distribution. These factors may introduce variations
in the observed runtime.

Understanding these factors and analyzing their impact on an algorithm's runtime is essential for
designing efficient algorithms, predicting performance, and making informed decisions when
selecting or optimizing algorithms for solving specific problems.
Q4] What is Algorithm? Explain criteria of Algorithms.

Ans: -

An algorithm is a step-by-step procedure or a set of rules for solving a specific problem or performing
a specific task. It is a well-defined sequence of instructions that takes an input, performs a series of
computational steps, and produces the desired output.

criteria of Algorithms: -

1. Input

• The algorithm must have zero or more inputs.

• These inputs are the values supplied externally to the algorithm before it begins.

✅ Example: Two numbers for an addition algorithm.

2. Output

• It must produce at least one output.

• The output is the result or solution obtained after processing the input.

✅ Example: Sum of two numbers.

3. Definiteness (Well-defined steps)

• Every step of the algorithm must be clearly and unambiguously defined.

• Instructions must be precise and understandable.

✅ Example: “Add 1 to x” is definite, but “do some processing” is not.

4. Finiteness

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

• It should not go into an infinite loop.

✅ Example: Looping 10 times is finite, while looping until a condition that never changes may be
infinite.

5. Effectiveness

• Each operation must be basic enough to be performed exactly and in a finite time.

• The steps must be feasible with the available resources.

✅ Example: Adding two numbers is effective, but solving an unsolvable puzzle is not.
Q5] What is Asymptotic Notations? Explain any three Asymptotic Notations.

Ans: -

Asymptotic notations are mathematical tools used to describe the growth rate of functions and
provide a standardized way to analyse the performance of algorithms. They are commonly used in
computer science and algorithm analysis to evaluate how the runtime or space requirements of an
algorithm grow with the size of the input.

There are three commonly used asymptotic notations:

1. Big O notation (O): It represents the upper bound or worst-case scenario of an algorithm's
time complexity. In simpler terms, it gives an upper limit on how much time an algorithm will take to
execute as the input size grows. For example, if an algorithm has a time complexity of O(n), it means
that the algorithm's runtime grows linearly with the input size or is at most proportional to the input
size.

2. Omega notation (Ω): It represents the lower bound or best-case scenario of an algorithm's
time complexity. It provides a lower limit on the growth rate of an algorithm as the input size
increases. For example, if an algorithm has a time complexity of Ω(n2), it means that the algorithm's
runtime grows at least quadratically with the input size.

3. Theta notation (Θ): It represents both the upper and lower bounds of an algorithm's time
complexity. It provides a tight bound on the growth rate of an algorithm. For example, if an algorithm
has a time complexity of Θ(n), it means that the algorithm's runtime grows linearly with the input
size, neither faster nor slower.

Q6] Define Max and Min Heap and write algorithm to insert into a heap.

Ans: -

🔹 Max Heap:
A Max Heap is a complete binary tree in which the value of each node is greater than or equal to the
values of its children.

• The maximum element is always at the root.

• Used in priority queues, heap sort, etc.

🛠️ Algorithm to Insert an Element into a Heap

➡️ Insertion into Max Heap

Steps:

1. Add the new element at the end of the heap (last position in array representation).

2. Compare the new element with its parent.

 3. If the new element is greater than the parent, swap them.

4. Repeat step 2 until the heap property is restored (heapify-up).

function insert Maxheap (heap, value):

heap. Append(value)

i = len(heap) - 1 while

i > 0:

parent = (i - 1) // 2 if

heap[parent] < heap[i]:

swap (heap, parent, i)

i = parent

else:

break

➡️ Insertion into Min Heap

Steps:

1. Add the new element at the end of the heap.

2. Compare the new element with its parent.

3. If the new element is less than the parent, swap them.

4. Repeat step 2 until the heap property is satisfied (heapify-up).

function insert Minheap (heap, value):

heap. Append(value)

i = len(heap) - 1

while i > 0:

parent = (i - 1) // 2 if

heap[parent] > heap[i]:

swap (heap, parent, i) i

= parent else:

break
Q7] What is max heap? Explain with example.

Ans: -

Max Heap is a special type of binary tree that satisfies two properties:

1. Complete Binary Tree Property:

The tree is completely filled on all levels except possibly the last, and all nodes are as far left
as possible.

2. Heap Property (Max Heap Property):

For every node i, the value of i is greater than or equal to the values of its children.

Example: -
Q8] Solve given recurrence relation by recursion tree method

T(n) = 3T(n/4) +cn2

Ans: -
Q9] Define Algorithm? State the main characteristics of Algorithm

Ans: -

An algorithm is a step-by-step procedure or a set of rules for solving a specific problem or performing
a specific task. It is a well-defined sequence of instructions that takes an input, performs a series of
computational steps, and produces the desired output.

characteristics of Algorithm: -

• Clear and Unambiguous: The algorithm should be unambiguous. Each of its steps should be
clear in all aspects and must lead to only one meaning.

• Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs. It

may or may not take input.

• Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it
should be well-defined as well. It should produce at least 1 output.

• Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.

• Feasible: The algorithm must be simple, generic, and practical, such that it can be executed
with the available resources. It must not contain some future technology or anything.

• Language Independent: The Algorithm designed must be language-independent, i.e. it must

be just plain instructions that can be implemented in any language, and yet the output will
be the same, as expected.

• Input: An algorithm has zero or more inputs. Each that contains a fundamental operator
must accept zero or more inputs.

• Output: An algorithm produces at least one output. Every instruction that contains a
fundamental operator must accept zero or more inputs.

• Definiteness: All instructions in an algorithm must be unambiguous, precise, and easy to

interpret. By referring to any of the instructions in an algorithm one can clearly understand
what is to be done. Every fundamental operator in instruction must be defined without any
ambiguity.

• Finiteness: An algorithm must terminate after a finite number of steps in all test cases. Every
instruction which contains a fundamental operator must be terminated within a finite
amount of time. Infinite loops or recursive functions without base conditions do not possess
finiteness.

• Effectiveness: An algorithm must be developed by using very basic, simple, and feasible
operations so that one can trace it out by using just paper and pencil.
Q10] Describe Asymptotic notations with expression

Ans: -
Q11] Solve the following recurrence relation using master method.

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

(ii) T(n) = 4T (n / 2) + n ^ 2

(ii) T(n) = 4T (n / 2) + n ^ 3

Ans: -
Q12] Define algorithm. What is the need of algorithm analysis? Which factor affect runtime of
algorithm?

Ans: -

1. Definition of Algorithm:

An algorithm is a step-by-step procedure or a set of rules for solving a specific problem or performing
a specific task. It is a well-defined sequence of instructions that takes an input, performs a series of
computational steps, and produces the desired output.

2. Need for Algorithm Analysis:

Algorithm analysis is crucial for several reasons:

- Efficiency Evaluation: It helps us understand and evaluate the efficiency of an algorithm in

terms of its resource usage, such as time and space. By analyzing the algorithm's runtime and
memory requirements, we can identify potential bottlenecks, optimize the algorithm, and select the
most suitable algorithm for a given problem.

- Performance Comparison: Algorithm analysis allows us to compare different algorithms for

the same problem. It enables us to determine which algorithm is more efficient in terms of time or
space complexity, aiding in the selection of the most appropriate solution for a specific problem
instance.

- Scalability Assessment: Algorithm analysis helps predict how an algorithm will perform as the
input size grows. It provides insights into the algorithm's behaviour and allows us to determine
whether it can handle larger problem instances efficiently.

- Algorithm Design and Improvement: Analysis of algorithms provides insights into the
strengths and weaknesses of existing algorithms. It helps identify areas for improvement, refine
algorithmic techniques, and design more efficient algorithms.

3. Factors Affecting Runtime of an Algorithm:

The runtime of an algorithm is influenced by several factors:

- Input Size: As the size of the input increases, the runtime of the algorithm typically grows.
The relationship between the input size and the algorithm's runtime is often expressed using Big O
notation.

- Algorithm Design: The design choices made within an algorithm can significantly impact its
runtime. Different algorithms may have varying approaches to solving a problem, resulting in
different runtime characteristics.

- Computational Steps: The number and complexity of computational steps performed by an

algorithm affect its runtime. The more computations or iterations an algorithm requires, the longer
its runtime is likely to be.

- Data Structures and Operations: The choice of data structures and the operations performed
on them can affect runtime. Different data structures have varying time complexities for operations
such as insertion, deletion, search, and traversal, which impact the overall runtime of an algorithm.
- External Factors: The runtime of an algorithm can also be influenced by external factors such
as hardware capabilities, system load, and input distribution. These factors may introduce variations
in the observed runtime.

Understanding these factors and analyzing their impact on an algorithm's runtime is essential for
designing efficient algorithms, predicting performance, and making informed decisions when
selecting or optimizing algorithms for solving specific problems.