The Recursion Tree Method is a visual technique used to solve recurrence relations, which arise in the analysis of recursive algorithms. It helps in determining the time complexity of recursive algorithms by breaking down the problem into smaller subproblems and visualizing the cost at each level of recursion.<h2>Key Concepts of Recursion Tree Method​ </h2><ol><li style="background-color: transparent">Recurrence Relation: <ul><li style="background-color: transparent">A recurrence relation expresses the running time of a recursive algorithm in terms of the size of the input (n) and the time taken by its subproblems.</li><li style="background-color: transparent">Example: T(n) = aT(n/b) + f(n)<ul><li style="background-color: transparent"><code>a</code>: Number of subproblems.</li><li style="background-color: transparent"><code>n/b</code>: Size of each subproblem.</li><li style="background-color: transparent"><code>f(n)</code>: Cost of dividing the problem and combining results.</li></ul></li></ul></li><li>Purpose of Recursion Tree:<ul><li style="background-color: transparent">To visualize how the recurrence relation expands.</li><li style="background-color: transparent">To calculate the total cost of the algorithm by summing up the costs at all levels of recursion.</li></ul></li><li style="background-color: transparent">Steps to Solve Using Recursion Tree:<ul><li style="background-color: transparent">Step 1: Expand the recurrence relation into a tree structure.</li><li style="background-color: transparent">Step 2: Calculate the cost at each level of the tree.</li><li style="background-color: transparent">Step 3: Sum up the costs of all levels to find the total cost.</li><li style="background-color: transparent">Step 4: Use asymptotic notation (Big O) to express the time complexity.</li></ul></li></ol><h2> </h2><h2>How to Use the Recursion Tree Method </h2> <h4>Example 1: Solve T(n) = 2T(n/2) + n</h4><ol><li style="background-color: transparent">Expand the Recurrence:<ul><li style="background-color: transparent">At the root (Level 0), the cost is <code>n</code>.</li><li style="background-color: transparent">At Level 1, the recurrence splits into 2 subproblems, each of size <code>n/2</code>. The cost at this level is <code>2 × (n/2) = n</code>.</li><li style="background-color: transparent">At Level 2, each subproblem splits again into 2 subproblems of size <code>n/4</code>. The cost is <code>4 × (n/4) = n</code>.</li><li style="background-color: transparent">This process continues until the subproblem size becomes 1.</li></ul></li><li style="background-color: transparent">Visualize the Tree:<div class="se-component se-image-container __se__float-none" style="width: 100%"><figure style="width: 100%;"><img src="https://www.api.ignoustudyadda.com/upload/editor-image/recursive-tree_1751200309231.png" alt="Recursive tree" data-rotate="" data-proportion="true" data-size="100%," data-align="none" data-percentage="100," data-file-name="recursive-tree.png" data-file-size="23905" data-origin="," style="width: 100%;"></figure></div></li><li style="background-color: transparent">Calculate the Total Cost:<ul><li style="background-color: transparent">Cost at each level = <code>n</code>.</li><li style="background-color: transparent">Number of levels = log₂n (since the size of the subproblem reduces by half at each level).</li><li style="background-color: transparent">Total cost = Cost per level × Number of levels = <code>n × log₂n</code>.</li></ul></li><li style="background-color: transparent">Final Complexity:<ul><li style="background-color: transparent">T(n) = O(n log n).</li></ul></li></ol>​ <h2>Example 2: Solve T(n) = T(n/2) + n </h2>Expand the Recurrence:<ul><li style="background-color: transparent">At Level 0, the cost is <code>n</code>.</li><li style="background-color: transparent">At Level 1, the cost is <code>n/2</code>.</li><li style="background-color: transparent">At Level 2, the cost is <code>n/4</code>.</li><li style="background-color: transparent">This continues until the subproblem size becomes 1.&nbsp;</li></ul>Visualize the Tree: <div class="se-component se-image-container __se__float-none"><figure><img src="https://www.api.ignoustudyadda.com/upload/editor-image/recursive-tree2_1751264700298.png" alt="Unbalanced Recursive tree" data-rotate="" data-proportion="true" data-size="," data-align="none" data-percentage="auto,auto" data-file-name="recursive-tree2.png" data-file-size="19756" data-origin="," style=""></figure></div> Calculate the Total Cost: <ol><li style="background-color: transparent">The costs form a geometric series: <code>n + n/2 + n/4 + ... + 1</code>.</li><li style="background-color: transparent">Sum of the series = 2n (approximation for infinite geometric series).</li></ol>Final Complexity: T(n) = O(n). <h3>Balanced Recursion Tree:</h3><ul><li style="background-color: transparent">If the recursion divides the problem into multiple subproblems of equal size (e.g., T(n) = 2T(n/2)), the tree is balanced.</li><li style="background-color: transparent">The total cost is often proportional to the number of levels multiplied by the cost at each level.</li></ul> <h3>Unbalanced Recursion Tree:</h3><ul><li style="background-color: transparent">If the recursion divides the problem into one smaller subproblem (e.g., T(n) = T(n/2)), the tree is unbalanced.</li><li style="background-color: transparent">The total cost is dominated by the cost at the root level.</li></ul> <h3>Advantages of Recursion Tree Method</h3><ul><li style="background-color: transparent">Visualization: Provides a clear picture of how the recurrence expands.</li><li style="background-color: transparent">Intuitive: Easy to understand and apply for simple recurrence relations.</li><li style="background-color: transparent">Useful for Divide-and-Conquer Algorithms: Helps analyze algorithms like Merge Sort, Quick Sort, and Binary Search.</li></ul> <h3>Limitations</h3><ul><li style="background-color: transparent">Not suitable for complex recurrence relations.</li><li style="background-color: transparent">Requires additional techniques (like Master Theorem) for precise analysis in some cases.&nbsp;</li></ul> <h3>Common Applications</h3><ol><li style="background-color: transparent">Merge Sort: T(n) = 2T(n/2) + O(n) → O(n log n)</li><li style="background-color: transparent">Binary Search: T(n) = T(n/2) + O(1) → O(log n)</li><li style="background-color: transparent">Matrix Multiplication (Strassen’s Algorithm): T(n) = 7T(n/2) + O(n²) → O(n^2.81)</li></ol>​

The Recursion-tree Method 

In this Notes I am going to cover all important topics. So that our students can get all study material in concise way and score best in the term exam.Below are the Chapters we will explore throughout this course.<h2>Block 1: </h2><ul><li>Basic of an Algorithm and its properties</li><li>Asymtotic Bounds</li><li>Complexity analysis of Algorithms</li><li>Recurrences</li></ul><h2>Block 2:</h2><ul><li>Greedy Technique </li><li>Divide &amp; Conquer Technique</li><li>Graph Algorithm i</li></ul><h2>Block 3: </h2><ul><li>Graph Algorithm ii </li><li>Dynamic Programming Technique</li><li>String Matching Technique</li></ul><h2>Block 4: </h2><ul><li>Introduction To Complexity Classes </li><li>NP-Completeness and NP Hard Problems</li><li>Handling Intractability</li></ul>

Home

Basic of an Algorithm and its properties

The Running time of an algorithm refers to the amount of time it takes for the algorithm to complete its execution as a function of the input size. It helps measure an algorithm's efficiency and predict its performance. For a given problem, more than one algorithm can be designed. However, one algorithm may be better than the other. To compare two algorithms for a problem, running time is generally used which is defined as the time taken by an algorithm in generating the output. An algorithm is better if it takes less running time. The “time” here is not necessarily the clock time. However, this measure should be invariant to any hardware used. Therefore, the running time of an algorithm can be represented in terms of the number of operations executed for a given input.This running time of an algorithm for producing the output is also known as time complexity.Therefore, two algorithms can be compared in terms of time complexity. an Algorithm is better compared to others having smaller running time (time complexity).&nbsp;Running time of an algorithm is represented as a function T(n), where n is the input size. Let, an algorithm has a running time T(n) = cn, where c is a constant. The running time for this algorithm is linearly dependent on the size of the input. The unit of T(n) is unspecified.<h2 style="line-height: 1.38">Determinants of Time Complexity</h2><ul><li style="font-size: 21px;color: rgb(39, 59, 104)">Input Size (n): The input variables for the algorithm, that is, the amount of information and the total number of variables.</li><li style="font-size: 21px;color: rgb(39, 59, 104)">Operations Count: The total number of operations that the algorithm will be able to accomplish such as multiplication, addition and comparison.</li><li style="font-size: 21px;color: rgb(39, 59, 104)">Hardware: The system’s microprocessor’s speed, memory and other configurations.</li><li style="font-size: 21px;color: rgb(39, 59, 104)">Implementation Details: How the code is written, performance optimizations and libraries called by the code.</li></ul><h2 style="line-height: 1.38">Forms of Running Time in Brief</h2>Best Case: The best scenario is when the algorithm runs within a predefined time frame, assuming it takes the most approachable input.Worst Case: The worst scenario is when all the least-favorable inputs are fed to an algorithm in an attempt to maximize the time, making the algorithm inefficient.Average Case: The time frame estimated while taking the average input of an algorithm is said to be the Average Case. <h2>Evaluating the Duration of an Algorithm </h2>There are three basic asymptotic(i.e., when input size n which are used to express the running time of an algorithm in terms of function, whose domain is the set of natural numbers N={1,2,3,…..}. These are:<ul><li style="font-size:21px;color:#000000;background-color:transparent"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi mathvariant="normal">O</mi></mrow><annotation encoding="application/x-tex">\Omicron</annotation></semantics></math>O​(Big – 'Oh') [This notation is used to express Upper bound (maximum steps) required to solve a problem] .</li><li style="font-size:21px;color:#000000;background-color:transparent"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi mathvariant="normal">Ω</mi></mrow><annotation encoding="application/x-tex">\Omega</annotation></semantics></math>Ω​('Omega') [This notation is used to express Lower bound i.e. minimum (at least) steps required to solve a problem] </li><li style="font-size:21px;color:#000000;background-color:transparent"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi mathvariant="normal">Θ</mi></mrow><annotation encoding="application/x-tex">\Theta</annotation></semantics></math>Θ​('Theta') Notations.[Used to express both Upper &amp; Lower bound, called tight bound]</li></ul><h2 style="line-height: 1.38">Below are the generalized form of running time for the algorithms: </h2>Constant Time(O(1)): If the running time does not depend on the input size (n) then it is known as constant running time. It can be represented as&nbsp; <div class="se-component se-image-container __se__float-none" style="width: 75%"><figure style="width: 100%;"><img src="https://www.api.ignoustudyadda.com/upload/editor-image/constant-1_1736550533887.png" alt="Constant Time" data-rotate="" data-proportion="true" data-size="75%," data-align="none" data-percentage="75," data-file-name="constant-1.png" data-file-size="14235" data-origin="," origin-size="369,318" style="width: 100%;"></figure></div>Linear Time O(kn): If the time complexity is at most a constant factor times the size of the input, then it is known as linear time complexity and is presented as T(n) &lt;=kn where k is a constant or T(n) =O(n). An algorithm of this type of complexity generally completes the execution in a single pass.<div class="se-component se-image-container __se__float-none"><figure><img src="https://www.api.ignoustudyadda.com/upload/editor-image/linear-drawio_1736589291257.png" alt="Linear Time" data-rotate="" data-proportion="true" data-size="," data-align="none" data-percentage="auto,auto" data-file-name="linear-drawio.png" data-file-size="14028" data-origin="," origin-size="369,258" style=""></figure></div>Logarithmic Time(log(n)): If the time complexity of an algorithm is proportional to the logarithm of the input size, then it is known as logarithmic time complexity and depicted as O(log n)time. For example, the running time of a binary search algorithm is O(log n).<div class="se-component se-image-container __se__float-none"><figure><img src="https://www.api.ignoustudyadda.com/upload/editor-image/log-time_1736592996712.png" alt="Logarithmic Time" data-rotate="" data-proportion="true" data-size="," data-align="none" data-percentage="auto,auto" data-file-name="log-time.png" data-file-size="16294" data-origin="," origin-size="379,298" style=""></figure></div>Quadratic Time: (T(n)= O(n)2)- It occurs when the algorithm is having a pair of nested loops. The outer loop iterates O(n) time and for each iteration the inner loop takes O(n) time so we get O(n2 ) by multiplying these two factors of n. Practically this is useful for problem for small input size or elementary sorting algorithms. The worst case time complexity for Bubble sort, Insertion sort, Selection sort and insertion sort running time complexities are O(n2 ).<div class="se-component se-image-container __se__float-none"><figure><img src="https://www.api.ignoustudyadda.com/upload/editor-image/quadratic-time_1736593019404.png" alt="Quadratic Time" data-rotate="" data-proportion="true" data-size="," data-align="none" data-percentage="auto,auto" data-file-name="quadratic-time.png" data-file-size="15190" data-origin="," origin-size="365,298" style=""></figure></div>Cubic Time: (T(n)= O(n3 )): It often occurs when the algorithm is having there nested loops and each loop has a maximum n iterations. Let us have one interesting example which requires cubic time complexity. Suppose we are given n sets: S1, S2,….Sn. Size of each set is n (i.e. each set has n elements). The problem is to find whether some pairs of these sets are disjoint, i.e there are no common elements in these pairs and what is the time complexity ?<div class="se-component se-image-container __se__float-none"><figure><img src="https://www.api.ignoustudyadda.com/upload/editor-image/cubic-time_1736593039658.png" alt="Cubic Time" data-rotate="" data-proportion="true" data-size="," data-align="none" data-percentage="auto,auto" data-file-name="cubic-time.png" data-file-size="15200" data-origin="," origin-size="364,298" style=""></figure></div>Polynomial Time: (0(nk )):-This running time is obtained when the search over all subsets of a set of a size kin performed. To understand the complexity of running time we have to find how many distinct subsets of a size k of n elements of a set can be chosen. For that we have to take a combination of n elements taken k at a time .As an example let us consider a problem to find an independent set in a graph which can be defined as a set of nodes in which no pair of nodes have an edge between them. Let us formulate the independent set problem in the following way: given a constant k and a graph G having n nodes (vertices) , find an independent set of size k.<div class="se-component se-image-container __se__float-none"><figure><img src="https://www.api.ignoustudyadda.com/upload/editor-image/polynomial-time_1736593468159.png" alt="Plolynomial Time" data-rotate="" data-proportion="true" data-size="," data-align="none" data-percentage="auto,auto" data-file-name="polynomial-time.png" data-file-size="15145" data-origin="," origin-size="364,298" style=""></figure></div>Exponential Time: (O(kn )) Beyond the polynomial time complexity there are other two types of bounds :exponential time O(2N )and factorial time O(n!): let us refine the independent set problem that we are given a graph of a size n and want to find out an independent of a maximum value instead of some constant k which is less than n. The modified version of the pseudo-code is presented below.<div class="se-component se-image-container __se__float-none"><figure><img src="https://www.api.ignoustudyadda.com/upload/editor-image/exponential-time_1736593493736.png" alt="Exponential Time" data-rotate="" data-proportion="true" data-size="," data-align="none" data-percentage="auto,auto" data-file-name="exponential-time.png" data-file-size="14958" data-origin="," origin-size="364,288" style=""></figure></div><h2>Pseudo-code : Pseudo-code for finding an Independent Set of a graph</h2><blockquote>Input G(V,E)&nbsp;{ for each subset s of n number of nodes verify whether s is an independent set&nbsp;if s is the largest among all the subsets examined so for&nbsp;print “s is the largest independent set ”&nbsp;end if&nbsp;end for&nbsp;}end of code fragment </blockquote><div> </div><h2> </h2>

Running Time Of Algorithm

Following are the some commonly known problem types: <ul><li style="font-size:19px;color:#000000;background-color:transparent">Sorting&nbsp;&nbsp;</li><li style="font-size:19px;color:#000000;background-color:transparent">Searching&nbsp;&nbsp;</li><li style="font-size:19px;color:#000000;background-color:transparent">Graph problems&nbsp;&nbsp;</li><li style="font-size:19px;color:#000000;background-color:transparent">Combinatorial problems&nbsp;&nbsp;</li><li style="font-size:19px;color:#000000;background-color:transparent">Geometric problems&nbsp;&nbsp;</li><li style="font-size:19px;color:#000000;background-color:transparent">Numerical problems</li></ul><h2 style="line-height: 1.38">Sorting:</h2><h2 style="line-height: 1.38">The sorting is the process to arrange the given set of items in a certain order, assuming that the nature of the items allow such an ordering. For example, sorting a set of numbers in increasing or decreasing order and sorting the character strings, like names, in an alphabetical order.</h2><h2 style="line-height: 1.38">For any sorting algorithm following two characteristics are desirable:</h2>1. Stability&nbsp;A sorting algorithm is called stable if it does not change the relative positions of any two equal items of the input list. Say, in an input list, there are two equal item sat positions i and j where i&lt; j, then the final position of these items in thesorted list should also be k and l respectively, such that k&lt;l. That is thereshould not be any swapping among these equal items and should notinterchange their position with each other. 2. In-place.&nbsp;A sorting algorithm needs extra memory space to store elements during the swapping process. For a small set of items in a list, this constraint is not observable but, for an input list of large elements the required storage space is considerably large. An algorithm is said to be in-place if the required extra memory is not markable.Searching:Searching is finding an element, referred to as a search key, in a given set of items (may have the redundant value). Searching is one of the most important and frequently performed operations on any dataset/database.<h2>String Processing: </h2>String processing refers to techniques and operations performed on strings (sequences of characters) to extract, manipulate, or analyze textual data. It is a fundamental concept in programming and is used in various domains like data cleaning, natural language processing, pattern matching, and more. Applications of String Processing<ul><li style="font-size:19px;color:#000000;background-color:transparent">Text Parsing and Tokenization: Extracting meaningful components from a string.</li><li style="font-size:19px;color:#000000;background-color:transparent">Data Cleaning: Removing unwanted characters or formatting strings for uniformity.</li><li style="font-size:19px;color:#000000;background-color:transparent">Pattern Matching: Detecting and replacing patterns in strings using regular expressions.</li><li style="font-size:19px;color:#000000;background-color:transparent">Natural Language Processing (NLP): Analyzing and transforming textual data for AI/ML tasks.</li><li style="font-size:19px;color:#000000;background-color:transparent">Log Analysis: Extracting valuable insights from logs and text data.</li><li style="font-size:19px;color:#000000;background-color:transparent">Input Validation: Ensuring strings conform to expected formats (e.g., email validation).</li></ul><h2 style="line-height: 1.38">Graph Problems:</h2>Graph problems refer to a class of computational problems that involve graph data structures. A graph is a mathematical representation of a set of objects (called vertices or nodes) and the connections (called edges) between them. Graph problems are central to computer science and have applications in areas such as networking, social media, AI, logistics, and biology.<h3 style="line-height:1.38">Applications of Graph Problems</h3><ol><li style="font-size:19px;color:#000000;background-color:transparent">Social Networks: Finding friends, influencers, or communities.</li><li style="font-size: 19px;color: rgb(0, 0, 0);background-color: transparent">Transportation: Optimizing routes and traffic flow.</li><li style="font-size: 19px;color: rgb(0, 0, 0);background-color: transparent">Telecommunications: Designing efficient networks.</li><li style="font-size: 19px;color: rgb(0, 0, 0);background-color: transparent">Biology: Analyzing gene or protein interaction networks.</li><li style="font-size: 19px;color: rgb(0, 0, 0);background-color: transparent">Project Management: Dependency resolution and scheduling.</li></ol><h2 style="line-height: 1.38">Combinatorial Problems:</h2>Combinatorial problems involve finding, counting, or optimizing arrangements, combinations, or subsets of discrete structures such as numbers, sets, or graphs. These problems arise in various fields, including mathematics, computer science, operations research, and optimization.These types of problems have a combination of solutions i.e. more than one solution are possible. The aim of the combinatorial problems is to find permutations, combinations, or subsets, satisfying the given conditions. The travelling salesman problem, independent set and the graph-coloring problems can be categorized as examples of combinatorial problems.&nbsp;<h3 style="line-height:1.38">Applications of Combinatorial Problems</h3><ol><li style="font-size:19px;color:#000000;background-color:transparent">Cryptography: Secure key generation.</li><li style="font-size:19px;color:#000000;background-color:transparent">Scheduling: Assigning tasks optimally to resources.</li><li style="font-size:19px;color:#000000;background-color:transparent">Game Theory: Analyzing possible strategies.</li><li style="font-size:19px;color:#000000;background-color:transparent">Logistics: Vehicle routing and packing problems.</li><li style="font-size:19px;color:#000000;background-color:transparent">Bioinformatics: DNA sequencing and protein folding.</li></ol> <h2>Geometric Problems:</h2>Geometric problems involve solving computational or mathematical challenges related to shapes, points, lines, angles, surfaces, and volumes in 2D or 3D spaces. These problems have applications in computer graphics, robotics, CAD, computational geometry, and more.Following are widely known classic problems of computational geometry:1. The closest-pair problem&nbsp;The closest-pair problem is to find the closest pair out of a given set of points in the plane.&nbsp;2. The convex-hull problem&nbsp;In the convex-hull problem, the smallest convex polygon is to be constructed so that it includes all the points of a given set.<h3 style="line-height:1.38">Applications of Geometric Problems</h3><ol><li style="font-size:19px;color:#000000;background-color:transparent">Computer Graphics: Rendering and modeling.</li><li style="font-size:19px;color:#000000;background-color:transparent">Robotics: Pathfinding and obstacle avoidance.</li><li style="font-size:19px;color:#000000;background-color:transparent">GIS: Geographic information systems for map analysis.</li><li style="font-size:19px;color:#000000;background-color:transparent">Physics: Collision detection in simulations.</li><li style="font-size:19px;color:#000000;background-color:transparent">Astronomy: Analyzing celestial object positions.</li></ol>

Types Of Computational Problems

Problem Solving Technique

Some Useful Mathematical Functions and Notations

Asymptotic Analysis and Notations

Useful Theorem of Aymptotic Notation

<h3 style="line-height: 1.2">Theorem 2:&nbsp; </h3>iff(n)=&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>a</mi><mi>m</mi></msub><msup><mi>n</mi><mi>m</mi></msup><mo>+</mo><msub><mi>a</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub><msup><mi>n</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo></mrow><annotation encoding="application/x-tex">a_{m}n^{m }+ a_{m-1}n^{m-1}+ </annotation></semantics></math>am​nm+am−1​nm−1+&nbsp;.... .... ...&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>+</mo><msub><mi>a</mi><mn>1</mn></msub><mi>n</mi><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">+ a_{1}n+a_{0}</annotation></semantics></math>+a1​n+a0​Where<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>a</mi><mi>m</mi></msub></mrow><annotation encoding="application/x-tex">a_{m}</annotation></semantics></math>am​&nbsp;!= 0 and&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>a</mi><mi>i</mi></msub><mo>∈</mo><mi>R</mi></mrow><annotation encoding="application/x-tex">a_{i} \isin R</annotation></semantics></math>ai​∈R,then<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">Ω</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mi>m</mi></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n) = \Omega(n^m)</annotation></semantics></math>f(n)=Ω(nm)

Useful Theorem of Big Omega Notation

<h3 style="line-height: 1.2">Theorem 3:&nbsp; </h3>iff(n)=&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>a</mi><mi>m</mi></msub><msup><mi>n</mi><mi>m</mi></msup><mo>+</mo><msub><mi>a</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub><msup><mi>n</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo></mrow><annotation encoding="application/x-tex">a_{m}n^{m }+ a_{m-1}n^{m-1}+ </annotation></semantics></math>am​nm+am−1​nm−1+&nbsp;.... .... ...&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>+</mo><msub><mi>a</mi><mn>1</mn></msub><mi>n</mi><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">+ a_{1}n+a_{0}</annotation></semantics></math>+a1​n+a0​Where<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>a</mi><mi>m</mi></msub></mrow><annotation encoding="application/x-tex">a_{m}</annotation></semantics></math>am​&nbsp;!= 0 and&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mi>a</mi><mi>i</mi></msub><mo>∈</mo><mi>R</mi></mrow><annotation encoding="application/x-tex">a_{i} \isin R</annotation></semantics></math>ai​∈R,then<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mi>m</mi></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(n) = \Theta(n^m)</annotation></semantics></math>f(n)=Θ(nm)

Useful Theorem of Theta Notation

Polynomial Evaluation

Exponent Evaluation

​Linear search or sequential search is a very simple search algorithm which isused to search for a particular element in an array. Unlike binary searchalgorithm, in linear search algorithm, elements are not arranged in a particularorder. In this type of search, an element is searched in an array sequentiallyone by one. If a match is found then that particular item is returned and thesearch process stops. Otherwise, the search continues till the end of an array.The following steps are used in the linear search algorithm: <h2>How Linear Search Works</h2><blockquote>​Linear_ Search( A[ ], X)Step 1: Initialize i to 1Step 2: if i exceeds the end of an array then print “element not found” and ExitStep 3: if A[i] = X then Print “Element X Found at index i in the array” and Exit Step 4: Increment i and go to Step 2 </blockquote><h3>Algorithm Steps</h3>Initialize: Start at the beginning of the list (index 0).Iterate through the List:<ul><li style="font-size: 16px">For each element in the list:</li><ul><li style="font-size: 16px">Compare the current element with the target value.</li><li style="font-size: 16px">If the element equals the target, return the index (or the element itself, depending on the requirements).</li></ul></ul>Termination:<ul><li style="font-size: 16px">If the target is found, the search stops.</li><li style="font-size: 16px">If the end of the list is reached without finding the target, the algorithm indicates that the target is not present (often by returning -1 or null).</li></ul><h3>Pseudocode </h3><pre>​function linearSearch(array, target): for index from 0 to length(array) - 1: if array[index] == target: return index // Target found at this index return -1 // Target not found </pre><h2> </h2><h2>Time and Space Complexity</h2><h3>​Time Complexity: </h3><table class="se-table-layout-fixed"><thead><tr><th><div>Case</div></th><th><div>Best Case&nbsp;</div></th><th><div>Worst Case</div></th><th><div>Average Case</div></th></tr></thead><tbody><tr><td><div>Item is Present</div></td><td><div>O(1)</div></td><td><div>O(n)</div></td><td><div>O(n/2) = O(n)</div></td></tr><tr><td><div>Item is not Present</div></td><td><div>O(n)</div></td><td><div>O(n)</div></td><td><div>O(n)</div></td></tr></tbody></table><h3> </h3><h3>Space Complexity: </h3>​O(1) — Only a constant amount of extra memory is needed regardless of the size of the input.​

Linear Search

<h2>Sorting</h2>Sorting is the process of arranging a collection of data into either ascending or descending order. Generally the output is arranged in sorted order so that it can be easily interpreted. Sometimes sorting at the initial stages increases the performances of an algorithm while solving a problem. Sorting techniques are broadly classified into two categories: <ol><li style="font-size: 18px">Internal Sort: - Internal sorts are the sorting algorithms in which the complete data set to be sorted is available in the computer’s main memory. Below are the list of some internal Sorting algorithms: i. Bubble Sort ii. Selection Sort iii. Insertion Sort</li></ol><ol><li style="font-size: 18px">External Sort: - External sorting techniques are used when the collection of complete data cannot reside in the main memory but must reside in secondary storage for example on a disk. </li></ol><h3>Bubble Sort: </h3>It is the simplest sorting algorithm in which each pair of adjacent elements is compared and exchanged if they are not in order. This algorithm is not recommended for use for a bigger size array because its average and worst case complexity are of Ο(n2) where n is the number of elements in an array.This algorithm is known as bubble sort, because the largest element in the given unsorted array, bubbles up towards the last place in every cycle/pass . I am going to demonstrate through tabluar viewFirst Pass<table class="se-table-layout-fixed"><tbody><tr><td><div>23</div></td><td><div>18</div></td><td><div>15</div></td><td><div>37</div></td><td><div>8 </div></td><td><div>11</div></td></tr><tr><td><div>18</div></td><td><div>23​</div></td><td><div>15</div></td><td><div>37</div></td><td><div>8</div></td><td><div>11</div></td></tr><tr><td><div>18</div></td><td><div>15</div></td><td><div>23</div></td><td><div>37</div></td><td><div>8</div></td><td><div>11</div></td></tr><tr><td><div>18</div></td><td><div>15</div></td><td><div>23</div></td><td><div>37</div></td><td><div>8</div></td><td><div>11</div></td></tr><tr><td><div>18</div></td><td><div>15</div></td><td><div>23</div></td><td>8</td><td><div>37</div></td><td><div>11</div></td></tr><tr><td><div>18</div></td><td><div>15</div></td><td><div>23</div></td><td><div>8</div></td><td><div>11</div></td><td><div>37 </div></td></tr></tbody></table>Second Pass<table class="se-table-layout-fixed"><tbody><tr><td><div>18</div></td><td><div>15</div></td><td><div>23</div></td><td><div>8</div></td><td><div>11</div></td><td><div>37</div></td></tr><tr><td><div>15</div></td><td><div>18</div></td><td><div>23</div></td><td><div>8</div></td><td><div>11</div></td><td><div>37</div></td></tr><tr><td><div>15</div></td><td><div>18</div></td><td><div>23</div></td><td><div>8</div></td><td><div>11</div></td><td><div>37</div></td></tr><tr><td><div>15</div></td><td><div>18</div></td><td>8</td><td>23</td><td><div>11</div></td><td>37</td></tr><tr><td><div>15</div></td><td><div>18</div></td><td><div>8</div></td><td><div>11</div></td><td><div>23</div></td><td><div>37</div></td></tr></tbody></table>Third Pass<table class="se-table-layout-fixed"><tbody><tr><td><div>15</div></td><td><div>18</div></td><td><div>8</div></td><td><div>11</div></td><td><div>23</div></td><td><div>37</div></td></tr><tr><td><div>15</div></td><td><div>18</div></td><td><div>8</div></td><td><div>11</div></td><td><div>23</div></td><td><div>37</div></td></tr><tr><td><div>15</div></td><td><div>8</div></td><td><div>18</div></td><td><div>11</div></td><td><div>23</div></td><td><div>37</div></td></tr><tr><td><div>15</div></td><td><div>8</div></td><td><div>11</div></td><td><div>18</div></td><td><div>23</div></td><td><div>37</div></td></tr></tbody></table>Fourth&nbsp;Pass<table class="se-table-layout-fixed"><tbody><tr><td><div>15</div></td><td><div>8</div></td><td><div>11</div></td><td><div>18</div></td><td><div>23</div></td><td><div>37</div></td></tr><tr><td><div>8</div></td><td><div>15</div></td><td><div>11</div></td><td><div>18</div></td><td><div>23</div></td><td><div>37</div></td></tr><tr><td><div>8</div></td><td><div>11</div></td><td><div>15</div></td><td><div>18</div></td><td><div>23</div></td><td><div>37</div></td></tr></tbody></table>Fifth Pass<table class="se-table-layout-fixed"><tbody><tr><td><div>8</div></td><td><div>11</div></td><td><div>15</div></td><td><div>18</div></td><td><div>23</div></td><td>37</td></tr><tr><td><div>8</div></td><td><div>11</div></td><td><div>15</div></td><td><div>18</div></td><td><div>23</div></td><td><div>37</div></td></tr></tbody></table><table class="se-table-layout-fixed"><tbody><tr><td><div>8</div></td><td><div>11</div></td><td><div>15</div></td><td><div>18</div></td><td><div>23</div></td><td><div>37</div></td></tr></tbody></table><h3>Pseudo Code:</h3><pre> public void bubbleSort(int[] arr) { int n = arr.length; boolean swapped; // Repeat the process until no swaps are made in a pass do { swapped = false; // Loop through the array elements for (int i = 0; i &lt; n - 1; i++) { // If the current element is greater than the next element, swap them if (arr[i] &gt; arr[i + 1]) { // Swap arr[i] and arr[i+1] int temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; // Mark that a swap occurred during this pass swapped = true; } } // Optionally, you can reduce 'n' here since the largest element is in place after each pass. } while (swapped); } </pre> <h2>Complexity Analysis</h2><ul><li>Time Complexity:<ul><li>Worst-case:&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2)​(occurs when the list is sorted in reverse order).</li><li style="font-size: 18px">Best-case:O(n)O(n)&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math>O(n)​ (occurs when the list is already sorted; with the optimization that stops if no swaps occur).</li><li style="font-size: 18px">Average-case:O(n2)O(n^2)&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2)​.</li></ul></li><li style="font-size: 18px">Space Complexity: O(1)O(1)<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1)​&nbsp;– Bubble sort is an in-place sorting algorithm, meaning it requires only a constant amount of additional memory.</li></ul>

Sorting Algorithms

A recursive algorithm is an algorithm that solves a problem by reducing it to smaller instances of the same problem. Instead of iterating through a sequence of operations, a recursive algorithm calls itself with a modified parameter until it reaches a condition that can be solved directly (known as the base case). Once the base case is reached, the algorithm begins to return results back through the chain of recursive calls.There are 2 components that play vital role to solve problem by Recursion.Base Condition:The condition under which the recursive calls stop. It provides a simple, non-recursive solution that terminates the recursion. Recursive Step:The part of the algorithm where the problem is divided into one or more smaller subproblems. The algorithm calls itself to solve these subproblems. <h2>Example: Factorial Function</h2><h3>Algorithm </h3><blockquote>​int factorial(int n)1: 𝑖𝑓 𝑛 == 0 𝑡ℎ𝑒𝑛2: 𝑟𝑒𝑡𝑢𝑟𝑛 13: 𝑒𝑙𝑠𝑒4: 𝑟𝑒𝑡𝑢𝑟𝑛 𝑛 ∗ (𝑛 − 1)5: endif </blockquote><h3>Mathematical Representation</h3> <math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>f</mi><mi>a</mi><mi>c</mi><mi>t</mi><mi>o</mi><mi>r</mi><mi>i</mi><mi>a</mi><mi>l</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mrow><mo fence="true">{</mo><mtable rowspacing="0.36em" columnalign="left left" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>1</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext>if&nbsp;</mtext><mi>n</mi><mo>=</mo><mn>0</mn></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>n</mi><mo>∗</mo><mi>f</mi><mi>a</mi><mi>c</mi><mi>t</mi><mi>o</mi><mi>r</mi><mi>i</mi><mi>a</mi><mi>l</mi><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext>if&nbsp;</mtext><mi>n</mi><mo>&gt;</mo><mn>0</mn></mrow></mstyle></mtd></mtr></mtable></mrow></mrow><annotation encoding="application/x-tex">factorial(n) = \begin{cases} 1 &amp;\text{if } n=0 \\ n * factorial(n-1) &amp;\text{if } n &gt;0\end{cases}</annotation></semantics></math>factorial(n)={1n∗factorial(n−1)​if&nbsp;n=0if&nbsp;n&gt;0​​ <h3>Pseudo Code </h3><pre>​function factorial(n): if n == 0: return 1 // Base case else: return n * factorial(n - 1) // Recursive case</pre>

Solving Recurences

There are several methods for solving recurrence relations, each suited to different types of recurrences. Here are the most common methods: <h2>1.&nbsp;Substitution Method</h2>​Substitution is opposite of induction .We start at n and move backward. A substitution method is one, in which we guess a bound and then use mathematical induction to prove whether our guess is correct or not?. It comprises two steps: Step1: Guess the asymptotic bound of the Solution.Step2: Prove the correctness of the guess using Mathematical Induction.Example 1. Solve the following recurrence by using substitution method. <math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>T</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mn>2</mn><mi>T</mi><mrow><mo fence="true">(</mo><mstyle displaystyle="false" scriptlevel="0"><mfrac linethickness="0.1em"><mi>n</mi><mn>2</mn></mfrac></mstyle><mo fence="true">)</mo></mrow><mo>+</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">T(n) = 2T\genfrac ( ) {1pt}{1}n{2}+n</annotation></semantics></math>T(n)=2T(2n​)+n​Solution: step1: The given recurrence is quite similar to that of Merge Sort algorithm,Therefore, our guess to the solution is (𝑛) = 𝑂 (𝑛𝑙𝑜𝑔𝑛)Or (𝑛) ≤ 𝑐. 𝑛𝑙𝑜𝑔𝑛 Step2: Now we use mathematical Induction. Here our guess does not hold for n=1 because (1) ≤ 𝑐. 1𝑙𝑜𝑔1𝑖. 𝑒. (𝑛) ≤ 0 𝑤ℎ𝑖𝑐ℎ 𝑖𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑖𝑐𝑡𝑖𝑜𝑛 𝑤𝑖𝑡ℎ (1) = 1 Now for n=2(2) ≤ 𝑐. 2𝑙𝑜𝑔2 2 <math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mn>2</mn><mi>T</mi><mrow><mo fence="true">(</mo><mstyle displaystyle="false" scriptlevel="0"><mfrac linethickness="0.1em"><mn>2</mn><mn>2</mn></mfrac></mstyle><mo fence="true">)</mo></mrow><mo>+</mo><mn>2</mn><mo>≤</mo><mi>c</mi><mi mathvariant="normal">.</mi><mn>2</mn></mrow><annotation encoding="application/x-tex">2T\genfrac ( ) {1pt}{1}2{2}+2 \le c.2</annotation></semantics></math>2T(22​)+2≤c.2​2(1) + 2 ≤ 𝑐. 20 + 2 ≤ 𝑐. 2 2 ≤ 𝑐. 2 which is true. So (2) ≤ 𝑐. 𝑛𝑙𝑜𝑔𝑛 is True for n = 2 So(2) ≤ 𝑐. 𝑛𝑙𝑜𝑔𝑛 is True form = 2

Comments

MCS 211