FEDERAL UNIVERSITY OTUOKE, BAYELSA STATE.

COMPUTER SCIENCE AND INFORMATICS DEPARTMENT

ALGORITHMS – CSC 404

Introduction
Algorithms and Complexity Analysis is a fundamental course in computer science
that focuses on the design, analysis, and evaluation of algorithms used to solve
computational problems efficiently. An algorithm is a step-by-step procedure or set
of instructions designed to perform a specific task or solve a problem. As modern
computing systems continue to grow in scale and complexity, the need for efficient
algorithms becomes increasingly important in areas such as software development,
artificial intelligence, data processing, cybersecurity, and scientific computing.

This course introduces students to various algorithmic strategies, including sorting,

searching, recursion, divide-and-conquer, greedy methods, dynamic programming,
and graph algorithms. It also explores methods for measuring the performance of
algorithms in terms of time and space complexity. Using mathematical tools and
asymptotic notations such as Big O, Big Theta, and Big Omega, students learn how
to compare algorithms and determine their efficiency under different conditions.

In addition, the course examines computational complexity theory, which classifies

problems according to the resources required to solve them. Topics such as tractable
and intractable problems, NP-completeness, and optimization problems provide
deeper insight into the limitations of computation and the practical challenges faced
in computer science.

By the end of the course, students are expected to develop strong problem-solving
skills, understand how to design efficient algorithms, and apply analytical techniques
to evaluate algorithmic performance in real-world applications.
What is an Algorithm? Algorithm Basics
The word Algorithm means ”A set of finite rules or instructions to be followed in
calculations or other problem-solving operations ” Or ” A procedure for solving a
programming problem in a finite number of steps that frequently involves recursive
operations”.

Therefore, Algorithm refers to a sequence of finite steps to solve a particular

problem.

Use of the Algorithms:

Algorithms play a crucial role in various fields and have many applications. Some
of the key areas where algorithms are used include:
Computer Science: Algorithms form the basis of computer programming and are
used to solve problems ranging from simple sorting and searching to complex tasks
such as artificial intelligence and machine learning.
Mathematics: Algorithms are used to solve mathematical problems, such as finding
the optimal solution to a system of linear equations or finding the shortest path in a
graph.
Operations Research: Algorithms are used to optimize and make decisions in fields
such as transportation, logistics, and resource allocation.
Artificial Intelligence: Algorithms are the foundation of artificial intelligence and
machine learning, and are used to develop intelligent systems that can perform tasks
such as image recognition, natural language processing, and decision-making.
Data Science: Algorithms are used to analyze, process, and extract insights from
large amounts of data in fields such as marketing, finance, and healthcare.
These are just a few examples of the many applications of algorithms. The use of
algorithms is continually expanding as new technologies and fields emerge, making
it a vital component of modern society.
Algorithms can be simple and complex depending on what you want to achieve.

It can be understood by taking the example of cooking a new recipe. To cook a new
recipe, one reads the instructions and steps and executes them one by one, in the
given sequence. The result thus obtained is the new dish is cooked perfectly. Every
time you use your phone, computer, laptop, or calculator you are using Algorithms.
Similarly, algorithms help to do a task in programming to get the expected output.

The Algorithm designed are language-independent, i.e. they are just plain
instructions that can be implemented in any language, and yet the output will be the
same, as expected.
What is the need for algorithms?
1. Algorithms are necessary for solving complex problems efficiently and
effectively.
2. They help to automate processes and make them more reliable, faster, and
easier to perform.
3. Algorithms also enable computers to perform tasks that would be difficult or
impossible for humans to do manually.
4. They are used in various fields such as mathematics, computer science,
engineering, finance, and many others to optimize processes, analyze data,
make predictions, and provide solutions to problems.

What are the Characteristics of an Algorithm?

As one would not follow any written instructions to cook the recipe, but only the
standard one, similarly, not all written instructions for programming is an
algorithms. In order for some instructions to be an algorithm, it must have the
following characteristics:
• Clear and Unambiguous: The algorithm should be clear and 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.
Properties of Algorithm:
• It should terminate after a finite time.
• It should produce at least one output.
• It should take zero or more input.
• It should be deterministic means giving the same output for the same input case.
• Every step in the algorithm must be effective i.e. every step should do some work.
Types of Algorithms:
There are several types of algorithms available. Some important algorithms are:

1. Brute Force Algorithm: It is the simplest approach for a problem. A brute force
algorithm is the first approach that comes to finding when we see a problem.
2. Recursive Algorithm: A recursive algorithm is based on recursion. In this case,
a problem is broken into several sub-parts and called the same function again and
again.
3. Backtracking Algorithm: The backtracking algorithm basically builds the
solution by searching among all possible solutions. Using this algorithm, we keep
on building the solution following criteria. Whenever a solution fails we trace back
to the failure point and build on the next solution and continue this process till we
find the solution or all possible solutions are looked after.
4. Searching Algorithm: Searching algorithms are the ones that are used for
searching elements or groups of elements from a particular data structure. They can
be of different types based on their approach or the data structure in which the
element should be found.
5. Sorting Algorithm: Sorting is arranging a group of data in a particular manner
according to the requirement. The algorithms which help in performing this function
are called sorting algorithms. Generally sorting algorithms are used to sort groups of
data in an increasing or decreasing manner.
6. Hashing Algorithm: Hashing algorithms work similarly to the searching
algorithm. But they contain an index with a key ID. In hashing, a key is assigned to
specific data.
7. Divide and Conquer Algorithm: This algorithm breaks a problem into sub-
problems, solves a single sub-problem and merges the solutions together to get the
final solution. It consists of the following three steps:
• Divide
• Solve
• Combine
8. Greedy Algorithm: In this type of algorithm the solution is built part by part. The
solution of the next part is built based on the immediate benefit of the next part. The
one solution giving the most benefit will be chosen as the solution for the next part.
9. Dynamic Programming Algorithm: This algorithm uses the concept of using
the already found solution to avoid repetitive calculation of the same part of the
problem. It divides the problem into smaller overlapping subproblems and solves
them.
10. Randomized Algorithm: In the randomized algorithm we use a random number
so it gives immediate benefit. The random number helps in deciding the expected
outcome.
To learn more about the types of algorithms refer to the article about “Types of
Algorithms“.

Advantages of Algorithms:
• It is easy to understand.
• An algorithm is a step-wise representation of a solution to a given problem.
• In Algorithm the problem is broken down into smaller pieces or steps hence, it is
easier for the programmer to convert it into an actual program.
Disadvantages of Algorithms:
• Writing an algorithm takes a long time so it is time-consuming.
• Understanding complex logic through algorithms can be very difficult.
• Branching and Looping statements are difficult to show in Algorithms(imp).
How to Design an Algorithm?
In order to write an algorithm, the following things are needed as a pre-requisite:

1. The problem that is to be solved by this algorithm i.e. clear problem definition.
2. The constraints of the problem must be considered while solving the problem.
3. The input to be taken to solve the problem.
4. The output to be expected when the problem is solved.
5. The solution to this problem is within the given constraints.
Then the algorithm is written with the help of the above parameters such that it solves
the problem.

Example: Consider the example to add three numbers and print the sum.

• Step 1: Fulfilling the pre-requisites

As discussed above, in order to write an algorithm, its pre-requisites must be

fulfilled.
1. The problem that is to be solved by this algorithm: Add 3 numbers and
print their sum.
 2. The constraints of the problem that must be considered while solving the
problem: The numbers must contain only digits and no other characters.
3. The input to be taken to solve the problem: The three numbers to be added.
4. The output to be expected when the problem is solved: The sum of the
three numbers taken as the input i.e. a single integer value.
5. The solution to this problem, in the given constraints: The solution
consists of adding the 3 numbers. It can be done with the help of ‘+’ operator,
or bit-wise, or any other method.
• Step 2: Designing the algorithm
Now let’s design the algorithm with the help of the above pre-requisites:
Algorithm to add 3 numbers and print their sum:
1. START
2. Declare 3 integer variables num1, num2 and num3.
3. Take the three numbers, to be added, as inputs in variables num1, num2, and
num3 respectively.
4. Declare an integer variable sum to store the resultant sum of the 3 numbers.
5. Add the 3 numbers and store the result in the variable sum.
6. Print the value of the variable sum
7. END
• Step 3: Testing the algorithm by implementing it.
In order to test the algorithm, let’s implement it in C language.
Program:
C++
// C++ program to add three numbers

// with the help of above designed

// algorithm

#include <bits/stdc++.h>

using namespace std;

int main()

// Variables to take the input of

// the 3 numbers

int num1, num2, num3;

// Variable to store the resultant sum

int sum;
// Take the 3 numbers as input

cout << "Enter the 1st number: ";

cin >> num1;

cout << " " << num1 << endl;

cout << "Enter the 2nd number: ";

cin >> num2;

cout << " " << num2 << endl;

cout << "Enter the 3rd number: ";

cin >> num3;

cout << " " << num3;

 // Calculate the sum using + operator

// and store it in variable sum

sum = num1 + num2 + num3;

// Print the sum

cout << "\nSum of the 3 numbers is: "

<< sum;

return 0;

// This code is contributed by shivanisinghss2110

C
Java
Python3
C#
Javascript

Output
Enter the 1st number: 0

Enter the 2nd number: 0

Enter the 3rd number: -1577141152

Sum of the 3 numbers is: -1577141152

Here is the step-by-step algorithm of the code:

1. Declare three variables num1, num2, and num3 to store the three numbers to be
added.
2. Declare a variable sum to store the sum of the three numbers.
3. Use the cout statement to prompt the user to enter the first number.
4. Use the cin statement to read the first number and store it in num1.
5. Use the cout statement to prompt the user to enter the second number.
6. Use the cin statement to read the second number and store it in num2.
7. Use the cout statement to prompt the user to enter the third number.
8. Use the cin statement to read the third number and store it in num3.
9. Calculate the sum of the three numbers using the + operator and store it in the
sum variable.
[Link] the cout statement to print the sum of the three numbers.
[Link] main function returns 0, which indicates successful execution of the
program.
Time complexity: O(1)
Auxiliary Space: O(1)
One problem, many solutions: The solution to an algorithm can be or cannot be
more than one. It means that while implementing the algorithm, there can be more
than one method to implement it. For example, in the above problem to add 3
numbers, the sum can be calculated in many ways like:
• + operator
• Bit-wise operators
• . . etc

How to analyze an Algorithm?

For a standard algorithm to be good, it must be efficient. Hence the efficiency of an

algorithm must be checked and maintained. It can be in two stages:

1. Priori Analysis: “Priori” means “before”. Hence Priori analysis means checking
the algorithm before its implementation. In this, the algorithm is checked when
it is written in the form of theoretical steps. This Efficiency of an algorithm is
measured by assuming that all other factors, for example, processor speed, are
constant and have no effect on the implementation. This is done usually by the
algorithm designer. This analysis is independent of the type of hardware and
language of the compiler. It gives the approximate answers for the complexity of
the program.
2. Posterior Analysis: “Posterior” means “after”. Hence Posterior analysis means
checking the algorithm after its implementation. In this, the algorithm is checked
by implementing it in any programming language and executing it. This analysis
helps to get the actual and real analysis report about correctness(for every
possible input/s if it shows/returns correct output or not), space required, time
consumed etc. That is, it is dependent on the language of the compiler and the
type of hardware used.
What is Algorithm complexity and how to find it?
An algorithm is defined as complex based on the amount of Space and Time it
consumes. Hence the Complexity of an algorithm refers to the measure of the Time
that it will need to execute and get the expected output, and the Space it will need to
store all the data (input, temporary data and output). Hence these two factors define
the efficiency of an algorithm.

The two factors of Algorithm Complexity are:

• Time Factor: Time is measured by counting the number of key operations such
as comparisons in the sorting algorithm.
• Space Factor: Space is measured by counting the maximum memory space
required by the algorithm to run/execute.
Therefore the complexity of an algorithm can be divided into two types:
1. Space Complexity: The space complexity of an algorithm refers to the amount
of memory required by the algorithm to store the variables and get the result. This
can be for inputs, temporary operations, or outputs.
How to calculate Space Complexity?
The space complexity of an algorithm is calculated by determining the following 2
components:

• Fixed Part: This refers to the space that is definitely required by the algorithm.
For example, input variables, output variables, program size, etc.
• Variable Part: This refers to the space that can be different based on the
implementation of the algorithm. For example, temporary variables, dynamic
memory allocation, recursion stack space, etc.
Therefore Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where
 C is the fixed part and S(I) is the variable part of the algorithm, which depends
on instance characteristic I.
Example: Consider the below algorithm for Linear Search
Step 1: START
Step 2: Get n elements of the array in arr and the number to be searched in x
Step 3: Start from the leftmost element of arr[] and one by one compare x with
each element of arr[]
Step 4: If x matches with an element, Print True.
Step 5: If x doesn’t match with any of the elements, Print False.
Step 6: END
Here, There are 2 variables arr[], and x, where the arr[] is the variable part of n
elements and x is the fixed part. Hence S(P) = 1+n. So, the space complexity
depends on n(number of elements). Now, space depends on data types of given
variables and constant types and it will be multiplied accordingly.

2. Time Complexity: The time complexity of an algorithm refers to the amount of

time that is required by the algorithm to execute and get the result. This can be for
normal operations, conditional if-else statements, loop statements, etc.
How to calculate Time Complexity?
The time complexity of an algorithm is also calculated by determining the following
2 components:
• Constant time part: Any instruction that is executed just once comes in this part.
For example, input, output, if-else, switch, arithmetic operations etc.
• Variable Time Part: Any instruction that is executed more than once, say n
times, comes in this part. For example, loops, recursion, etc.

Therefore Time complexity of any algorithm P is T(P) = C + TP(I),

 where C is the constant time part and TP(I) is the variable part of the algorithm,
which depends on the instance characteristic I.
Example: In the algorithm of Linear Search above, the time complexity is
calculated as follows:
Step 1: –Constant Time
Step 2: — Variable Time (Taking n inputs)
Step 3: –Variable Time (Till the length of the Array (n) or the index of the found
element)
Step 4: –Constant Time
Step 5: –Constant Time
Step 6: –Constant Time
Hence, T(P) = 5 + n, which can be said as T(n).

How to express an Algorithm?

1. Natural Language:- Here we express the Algorithm in natural English language.
It is too hard to understand the algorithm from it.
2. Flow Chat :- Here we express the Algorithm by making graphical/pictorial
representation of it. It is easier to understand than Natural Language.
3. Pseudo Code :- Here we express the Algorithm in the form of annotations and
informative text written in plain English which is very much similar to the real
code but as it has no syntax like any of the programming language, it can’t be
compiled or interpreted by the computer. It is the best way to express an
algorithm because it can be understood by even a layman with some school level
programming knowledge.
How to Write an Algorithm?

There are no well-defined standards for writing algorithms. Rather, it is problem

and resource dependent. Algorithms are never written to support a particular
programming code.

As we know that all programming languages share basic code constructs like loops
(do, for, while), flow-control (if-else), etc. These common constructs can be used
to write an algorithm.

We write algorithms in a step-by-step manner, but it is not always the case.

Algorithm writing is a process and is executed after the problem domain is well-
defined. That is, we should know the problem domain, for which we are designing
a solution.

Example

Let's try to learn algorithm-writing by using an example.

Problem − Design an algorithm to add two numbers and display the result.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP
Algorithms tell the programmers how to code the program. Alternatively, the
algorithm can be written as −

Step 1 − START ADD

Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

In design and analysis of algorithms, usually the second method is used to describe
an algorithm. It makes it easy for the analyst to analyze the algorithm ignoring all
unwanted definitions. He can observe what operations are being used and how the
process is flowing.

Writing step numbers, is optional.

We design an algorithm to get a solution of a given problem. A problem can be

solved in more than one ways.
Hence, many solution algorithms can be derived for a given problem. The next step
is to analyze those proposed solution algorithms and implement the best suitable
solution.

Algorithm Analysis

Efficiency of an algorithm can be analyzed at two different stages, before

implementation and after implementation. They are the following −

• A Priori Analysis − This is a theoretical analysis of an algorithm. Efficiency

of an algorithm is measured by assuming that all other factors, for example,
processor speed, are constant and have no effect on the implementation.

• A Posterior Analysis − This is an empirical analysis of an algorithm. The

selected algorithm is implemented using programming language. This is then
executed on target computer machine. In this analysis, actual statistics like
running time and space required are collected.

We shall learn about a priori algorithm analysis. Algorithm analysis deals with the
execution or running time of various operations involved. The running time of an
operation can be defined as the number of computer instructions executed per
operation.

Algorithm Complexity

Suppose X is an algorithm and n is the size of input data, the time and space used
by the algorithm X are the two main factors, which decide the efficiency of X.

• Time Factor − Time is measured by counting the number of key operations

such as comparisons in the sorting algorithm.
 • Space Factor − Space is measured by counting the maximum memory space
required by the algorithm.

The complexity of an algorithm f(n) gives the running time and/or the storage space
required by the algorithm in terms of n as the size of input data.

Space Complexity

Space complexity of an algorithm represents the amount of memory space required

by the algorithm in its life cycle. The space required by an algorithm is equal to the
sum of the following two components −

• A fixed part that is a space required to store certain data and variables, that
are independent of the size of the problem. For example, simple variables and
constants used, program size, etc.

• A variable part is a space required by variables, whose size depends on the

size of the problem. For example, dynamic memory allocation, recursion
stack space, etc.

Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed
part and S(I) is the variable part of the algorithm, which depends on instance
characteristic I. Following is a simple example that tries to explain the concept −

Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop

Here we have three variables A, B, and C and one constant. Hence S(P) = 1 + 3.
Now, space depends on data types of given variables and constant types and it will
be multiplied accordingly.
Time Complexity

Time complexity of an algorithm represents the amount of time required by the

algorithm to run to completion. Time requirements can be defined as a numerical
function T(n), where T(n) can be measured as the number of steps, provided each
step consumes constant time.

For example, addition of two n-bit integers takes n steps. Consequently, the total
computational time is T(n) = c ∗ n, where c is the time taken for the addition of two
bits. Here, we observe that T(n) grows linearly as the input size increases.
1.1 What is an algorithm?
An algorithm is an explicit, precise, unambiguous, mechanically-executable
sequence of elementary instructions.

An algorithm is the step-by-step unambiguous instructions to solve a given problem.

In the traditional study of algorithms, there are two main criteria for judging the
merits of algorithms: correctness (does the algorithm give solution to the problem in
a finite number of steps?) and efficiency (how much resources (in terms of memory
and time) does it take to execute the algorithm).

1.2 Writing down algorithms

Computer programs are concrete representations of algorithms, but algorithms are
not programs; they should not be described in a particular programming language.
The whole point of this course is to develop computational techniques that can be
used in any programming language.
The idiosyncratic syntactic details of C, C++, C#, Java, Python, Ruby, Erlang,
Haskell, OcaML, Scheme, Scala, Clojure, Visual Basic, Smalltalk, Javascript,
Processing, Squeak, Forth, TEX, Fortran, COBOL, INTERCAL, MMIX,
LOLCODE, Befunge, Parseltongue, Whitespace, or Brainfuck are of little or no
importance in algorithm design, and focusing on them will only distract you from
what’s really going on.¹¹ What we really want is closer to what you’d write in the
comments of a real program than the code itself.
On the other hand, a plain English prose description is usually not a good idea either.
Algorithms have lots of structure—especially conditionals, loops, and recursion—
that are far too easily hidden by unstructured prose. Natural languages like English
are full of ambiguities, subtleties, and shades of meaning, but algorithms must be
described as precisely and unambiguously as possible.

What is Pseudo-Code?• A mixture of natural language and high-level programming

concepts that describes the main ideas behind a generic implementation of a data
structure or algorithm.
- Expressions: use standard mathematical symbols to describe numeric and Boolean
expressions
- use for assignment (“=” in Java)
- use = for the equality relationship (“==” in Java)
- Method Declarations:
- Algorithm name(param1, param2)
- Programming Constructs:
- decision structures: if ... then ... [else ... ]
- while-loops: while ... do
- repeat-loops: repeat ... until ...
- for-loop: for ... do
- array indexing: A[i]
- Methods:
- calls: object method(args)
- returns: return value

The clearest way to present an algorithm is using pseudocode. Pseudocode uses the
structure of formal programming languages and mathematics to break algorithms
into primitive steps; but the primitive steps themselves may be written using
mathematics, pure English, or an appropriate mixture of the two. Well-written
pseudocode reveals the internal structure of the algorithm but hides irrelevant
implementation details, making the algorithm much easier to understand, analyze,
debug, and implement.
The precise syntax of pseudocode is a personal choice, but the overriding goal
should be clarity and precision. Ideally, pseudocode should allow any
competent programmer to implement the underlying algorithm, quickly and
correctly, in their favorite programming language, without understanding why
the algorithm works. Here are the guidelines to follow and it is strongly
recommended
:
• Be consistent!
• Use standard imperative programming keywords (if/then/else, while, for,
repeat/until, case, return) and notation (variable value, Array[index],
function(argument), bigger > smaller, etc.). Keywords should be standard English
words: write ‘else if’ instead of ‘elif’.
• Indent everything carefully and consistently; the block structure should be visible
from across the room. This rule is especially important for nested loops and
conditionals. Don’t add unnecessary syntactic sugar like braces or begin/end tags;
careful indentation is almost always enough.

• Use mnemonic algorithm and variable names.

Short variable names are good, but readability is more important than concision;
except for idioms like loop indices, short but complete words are better than single
letters. Absolutely never use pronouns!
 • Use standard mathematical notation for standard mathematical things. For
example, write x · y instead of x _ y for multiplication; write x mod y instead of x%
y for remainder; write px instead of sqrt(x) for square roots; write ab instead of
power(a, b) for exponentiation; and write _ instead of phi for the golden ratio.
• Avoid mathematical notation if English is clearer. For example, ‘Insert a into X’
may be preferable to Insert(X, a) or X X [ {a}].
• Each statement should fit on one line, and each line should contain either exactly
one statement or exactly one structuring element (for, while, if). (I sometimes make
an exception for short and similar statements like i i + 1; j j − 1; k 0.)
• Don’t use a fixed-width typeface to typeset pseudocode; it’s much harder to read
than normal typeset text. Similarly, don’t typeset keywords like ‘for’ or ‘while’ in a
different style; the syntactic sugar is not what you want the reader to look at. On the
other hand, I do use italics for variables (following the standard mathematical
typesetting convention), Small Caps for algorithms and constants, and a different
typeface for literal strings.

Algorithm types we will consider include:

• Simple recursive algorithms.

• Backtracking algorithms.
• Divide and conquer algorithms.
• Dynamic programming algorithms.
• Greedy algorithms.
• Branch and bound algorithms.
• Brute force algorithms.
• Randomized algorithms.
1. Simple Recursive Algorithm
Recursion is a method of solving a problem where the solution depends on solutions
to smaller instances of the same problem. Such problems can generally be solved by
iteration, but this needs to identify and index the smaller instances at programming
time.

Recursive algorithm is a method of simplification that divides the problem into

sub-problems of the same nature. ... Generation of factorial, Fibonacci number
series are the examples of recursive algorithms.

Basic steps of recursive programs

1. Initialize the algorithm. ...

2. Check to see whether the current value(s) being processed match the base
case. ...
3. Redefine the answer in terms of a smaller or simpler sub-problem or sub-
problems.
4. Run the algorithm on the sub-problem.
5. Combine the results in the formulation of the answer.
Different types of the recursion

• Direct Recursion.
• Indirect Recursion.
• Tail Recursion.
• No Tail/ Head Recursion.
• Linear recursion.
• Tree Recursion.

Recursion is a tool not often used by imperative language developers because it is

thought to be slow and to waste space. But as you’ll see, there are several
techniques that can be used to minimize or eliminate these problems. This article
introduces the concept of recursion and tackles recursive programming patterns,
examining how they can be used to write provably correct programs. Examples are
in Scheme and C.

For new computer science students, the concept of recursive programming is often
difficult. Recursive thinking is difficult because it almost seems like circular
reasoning. It’s also not an intuitive process; when we give instructions to other
people, we rarely direct them recursively.

For those of you who are new to computer programming, here’s a simple definition
of recursion: Recursion occurs when a function calls itself directly or indirectly.

A classic example of recursion

The classic example of recursive programming involves computing factorials. The
factorial of a number is computed as that number times all of the numbers below it
up to and including 1. For example, factorial(5) is the same as 5*4*3*2*1,
and factorial(3) is 3*2*1.

An interesting property of a factorial is that the factorial of a number is equal to the

starting number multiplied by the factorial of the number immediately below it.
For example, factorial(5) is the same as 5 * factorial(4). You could almost write
the factorial function simply as this:

Listing 1. First try at factorial function

int factorial(int n)
{
return n * factorial(n - 1);
}
Show more

The problem with this function, however, is that it would run forever because there
is no place where it stops. The function would continually call factorial. There is
nothing to stop it when it hits zero, so it would continue calling factorial on zero
and the negative numbers. Therefore, our function needs a condition to tell it when
to stop.

Since factorials of numbers less than 1 don’t make any sense, we stop at the number
1 and return the factorial of 1 (which is 1). Therefore, the real factorial function
will look like this:
Listing 2. Actual factorial function
int factorial (int n)
{
if(n == 1)
{
return 1;
}
else
{
return n * factorial(n - 1);
}
}

As you can see, as long as the initial value is above zero, this function will
terminate. The stopping point is called the base case. A base case is the bottom
point of a recursive program where the operation is so trivial as to be able to return
an answer directly. All recursive programs must have at least one base case and
must guarantee that they will hit one eventually; otherwise the program would run
forever or until the program ran out of memory or stack space.

Basic steps of recursive programs

Every recursive program follows the same basic sequence of steps:

1. Initialize the algorithm. Recursive programs often need a seed value to start
with. This is accomplished either by using a parameter passed to the function
 or by providing a gateway function that is non-recursive but that sets up the
seed values for the recursive calculation.
2. Check to see whether the current value(s) being processed match the base
case. If so, process and return the value.
3. Redefine the answer in terms of a smaller or simpler sub-problem or sub-
problems.
4. Run the algorithm on the sub-problem.
5. Combine the results in the formulation of the answer.
6. Return the results.

Using an inductive definition

Sometimes when writing recursive programs, finding the simpler sub-problem can
be tricky. Dealing with inductively-defined data sets, however, makes finding the
sub-problem considerably easier. An inductively-defined data set is a data structure
defined in terms of itself -- this is called an inductive definition.

For example, linked lists are defined in terms of themselves. A linked list consists
of a node structure that contains two members: the data it is holding and a pointer
to another node structure (or NULL, to terminate the list). Because the node
structure contains a pointer to a node structure within it, it is said to be defined
inductively.

With inductive data, it is fairly easy to write recursive procedures. Notice how like
our recursive programs, the definition of a linked list also contains a base case -- in
this case, the NULL pointer. Since a NULL pointer terminates a list, we can also
use the NULL pointer condition as a base case for many of our recursive functions
on linked lists.
Linked list example

Let’s look at a few examples of recursive functions on linked lists. Suppose we

have a list of numbers, and we want to sum them. Let’s go through each step of the
recursive sequence and identify how it applies to to our summation function:

1. Initialize the algorithm. This algorithm’s seed value is the first node to
process and is passed as a parameter to the function.
2. Check for the base case. The program needs to check and see if the current
node is the NULL list. If so, we return zero because the sum of all members
of an empty list is zero.
3. Redefine the answer in terms of a simpler sub-problem. We can define the
answer as the sum of the rest of the list plus the contents of the current node.
To determine the sum of the rest of the list, we call this function again with
the next node.
4. Combine the results. After the recursive call completes, we add the value of
the current node to the results of the recursive call.

Here is the pseudo-code and the real code for the function:

Listing 3. Pseudo-code for the sum_list program

function sum_list(list l)
is l null?
yes - the sum of an empty list is 0 - return that
data = head of list l
rest_of_list = rest of list l
the sum of the list is:
data + sum_list(rest_of_list)
Show more

The pseudo-code for this program almost identically matches its Scheme
implementation.

Listing 4. Scheme code for the sum_list program

(define sum-list (lambda (l)
(if (null? l)
0
(let (
(data (car l))
(rest-of-list (cdr l)))
(+ data (sum-list rest-of-list))))))
Show more

For this easy example, the C version is just as simple.

Listing 5. C code for the sum_list program

int sum_list(struct list_node *l)
{
if(l == NULL)
return 0;
return [Link] + sum_list([Link]);
}
Show more

You may be thinking that you know how write this program to perform faster or
better without recursion. We will get to the speed and space issues of recursion
later on. In the meantime, let’s continue our discussion of recursing of inductive
data sets.

Suppose we have a list of strings and want to see whether a certain string is
contained in that list. The way to break this down into a simpler problem is to look
again at the individual nodes.

The sub-problem is this: “Is the search string the same as the one in this node?” If
so, you have your solution; if not, you are one step closer. What’s the base case?
There are two:

• If the current node has the string, that’s a base case (returning “true”).
• If the list is empty, then that’s a base case (returning “false”).

This program won’t always hit the first base case because it won’t always have the
string being searched for. However, we can be certain that if the program doesn’t
hit the first base case it will at least hit the second one when it gets to the end of
the list.

Listing 6. Scheme code for determining if a given list contains a given string
(define is-in-list
(lambda (the-list the-string)
;;Check for base case of "list empty"
(if (null? the-list)
#f
;;Check for base case of "found item"
(if (equal? the-string (car the-list))
#t
;;Run the algorithm on a smaller problem
 (is-in-list (cdr the-list) the-string)))))
Show more

This recursive function works fine, but it has one main shortcoming -- every
iteration of the recursion will be passing the same value for the-string. Passing the
extra parameter can increase the overhead of the function call.

However, we can set up a closure at the beginning of the function to keep the string
from having to be passed on each call:

Listing 7. Scheme program for finding a string using a closure

(define is-in-list2
(lambda (the-list the-string)
(letrec
(
(recurse (lambda (internal-list)
(if (null? internal-list)
#f
(if (equal? the-string (car internal-list))
#t
(recurse (cdr internal-list)))))))
(recurse the-list))))
Show more

This version of the program is a little harder to follow. It defines a closure

called recurse that can be called with only one parameter rather than two. (For more
information on closures, see resouces on the right side.) We don’t need to pass
in the-string to recurse because it is already in the parent environment and does not
change from call to call. Because recurse is defined within the is-in-list2 function,
it can see all of the currently defined variables, so they don’t need to be re-passed.
This shaves off one variable being passed at each iteration.

Using a closure instead of passing the parameter doesn’t make a lot of difference
in this trivial example, but it can save a lot of typing, a lot of errors, and a lot of
overhead involved in passing variables in more complex functions.

The way of making recursive closures used in this example is a bit tedious. This
same pattern of creating a recursive closure using letrec and then calling it with an
initial seed value occurs over and over again in recursive programming.

In order to make programming recursive patterns easier, Scheme contains a

shortcut called the named let. This construct looks a lot like a let except that the
whole block is given a name so that it can be called as a recursive closure. The
parameters of the function built with the named let are defined like the variables in
a regular let; the initial seed values are set the same way initial variable values are
set in a normal let. From there, each successive recursive call uses the parameters
as new values.

Named let‘s are fairly confusing to talk about, so take a look at the following code
and compare it with the code in Listing 7.

Listing 8. Named let example

Listing 8. Named let example

(define is-in-list2
(lambda (the-list the-string)
;;Named Let
 ;;This let block defines a function called "recurse" that is the
;;body of this let. The function's parameters are the same as
;;the variables listed in the let.
(let recurse
;;internal-list is the first and only parameter. The
;;first time through the block it will be primed with
;;"the-list" and subsequent calls to "recurse" will
;;give it whatever value is passed to "recurse"
( (internal-list the-list) )

;;Body of function/named let block

(if (null? internal-list)
#f
(if (equal? the-string (car internal-list))
#t
;;Call recursive function with the
;;rest of the list
(recurse (cdr internal-list)))))))
Show more

The named let cuts down considerably on the amount of typing and mistakes made
when writing recursive functions. If you are still having trouble with the concept
of named lets, I suggest that you thoroughly compare every line in the above two
programs (as well as look at some of the documents in the resouces on the right
side of this article).

Our next example of a recursive function on lists will be a little more complicated.
It will check to see whether or not a list is in ascending order. If the list is in
ascending order, the function will return #t; otherwise, it will return #f. This
program will be a little different because in addition to having to examine the
current value, we will also have to remember the last value processed.

The first item on the list will have to be processed differently than the other items
because it won’t have any items preceding it. For the remaining items, we will need
to pass the previously examined data item in the function call. The function looks
like this:

Listing 9. Scheme program to determine whether a list is in ascending order

(define is-ascending
(lambda (the-list)
;;First, Initialize the algorithm. To do this we
;;need to get the first value, if it exists, and
;;use it as a seed to the recursive function
(if (null? the-list)
#t
(let is-ascending-recurse
(
(previous-item (car the-list))
(remaining-items (cdr the-list))
)
;;Base case #1 - end of list
(if (null? remaining-items)
#t
(if (< previous-item (car remaining-items))
;;Recursive case, check the rest of the list
(is-ascending-recurse (car remaining-items) (cdr remaining-items))
 ;;Base case #2 - not in ascending order
#f))))))
Show more

This program begins by first checking a boundary condition -- whether or not the
list is empty. An empty list is considered ascending. The program then seeds the
recursive function with the first item on the list and the remaining list.

Next, the base case is checked. The only way to get to the end of the list is if
everything so far has been in order, so if the list is empty, the list is in ascending
order. Otherwise, we check the current item.

If the current item is in ascending order, we then have only a subset of the problem
left to solve -- whether or not the rest of the list is in ascending order. So we recurse
with the rest of the list and try it again.

Notice in this function how we maintained state through function calls by passing
the program forward. Previously we had just passed the remainder of the list each
time. In this function though, we needed to know a little bit more about the state of
the computation. The result of the present computation depended on the partial
results before it, so in each successive recursive call, we pass those results forward.
This is a common pattern for more complex recursive procedures.

Writing provably correct programs

Bugs are a part of the daily life of every programmer because even the smallest
loops and the tiniest function calls can have bugs in them. And while most
programmers can examine code and test code for bugs, they do not know how to
prove that their programs will perform the way they think they will. With this in
mind, we are going to examine some of the common sources of bugs and then
demonstrate how to make programs which are correct and can be proven so.

Bug source: State changes

One of the primary sources of bugs occurs when variables change states. You might
think that the programmer would be keenly aware of exactly how and when a
variable changes state. This is sometimes true in simple loops, but usually not in
complex ones. Usually within loops, there are several ways that a given variable
can change state.

For example, if you have a complicated if statement, some branches may modify
one variable while others modify other variables. On top of that, the order is usually
important but it is difficult to be absolutely sure that the sequence coded is the
correct order for all cases. Often, fixing one bug for one case will introduce other
bugs in other cases because of these sequencing issues.

In order to prevent these kinds of errors, a developer needs to be able to:

• Tell by sight how each variable received its present value.

• Be certain that no variable is performing double-duty. (Many programmers
often use the same variable to store two related but slightly different values.)
• Be certain that all variables hit the state they are supposed to be in when the
loop restarts. (A common programming error is failure to set new values for
loop variables in corner cases that are rarely used and tested.)

To accomplish these objectives, we need to make only one rule in our

programming: Assign a value to a variable only once and NEVER MODIFY IT!
What? (You say increduluously!) This rule is blasphemy for many who have been
raised on imperative, procedural, and object-oriented programming -- variable
assignment and modification are at the core of these programming techniques!
Still, state changes are consistently one of the chief causes for programming errors
for imperative programmers.

So how does a person program without modifying variables? Let’s look at several
situations in which variables are often modified and see if we can get by without
doing so:

• Reusing a variable.
• Conditional modification of a variable.
• Loop variables.

Let’s examine the first case, reusing a variable. Often, a variable is reused for
different, but similar, purposes. For example, sometimes if part of a loop needs an
index to the current position in the first half of a loop and the index immediately
before or after for the rest of the loop, many programmers use the same variable
for both cases, just incrementing it in the middle. This can easily cause the
programmer to confuse the two uses as the program is modified. To prevent this
problem, the best solution is to create two separate variables and just derive the
second from the first the same way you would do so if you were just writing to the
same variable.

The second case, the conditional modification of a variable, is a subset of the

variable reuse problem except that sometimes we will keep our existing value and
sometimes we will want a new value. Again, the best thing is to create a new
variable. In most languages, we can use the tertiary operator ? : to set the value of
the new variable. For example, if we wanted to give our new variable a new value,
as long as it’s not greater than some_value, we could write int new_variable =
old_variable > some_value ? old variable : new_value;.

(We’ll discuss loop variables later in the article.)

Once we have rid ourselves of all variable state changes, we can know that when
we first define our variable, the definition of our variable will hold for as long as
the function lasts. This makes sequencing orders of operations much easier,
especially when modifying existing code. You don’t have to worry about what
sequence a variable might have been modified in or what assumptions were being
made about its state at each juncture.

When a variable cannot change state, the full definition of how it is derived is
illustrated when and where it is declared! You never have to go searching through
code to find the incorrect or misordered state change again!

What about loop variables

Now, the question is how to do loops without assignment? The answer lies
in recursive functions. Take a look at the properties of loops and see how they
compare with those of recursive functions in Table 1.

Table 1. Comparing loops with recursive functions

Properties Loops Recursive functions

Execute the same block of

code repeatedly to obtain Execute the same block of code
Repetition
the result; signal their repeatedly to obtain the result; signal
Properties Loops Recursive functions

intent to repeat by either their intent to repeat by calling

finishing the block of themselves.
code or issuing
a continue command.

In order to guarantee that

it will terminate, a loop
must have one or more
conditions that cause it to
terminate and it must be In order to guarantee that it will
guaranteed at some point terminate, a recursive function
Terminatingto hit one of these requires a base case that causes the
conditions conditions. function to stop recursing.

Current state is updated as

State the loop progresses. Current state is passed as parameters.

As you can see, recursive functions and loops have quite a bit in common. In fact,
loops and recursive functions can be considered interchangeable. The difference is
that with recursive functions, you rarely have to modify any variable -- you just
pass the new values as parameters to the next function call. This allows you to keep
all of the benefits of not having an updateable variable while still having repetitive,
stateful behavior.
Converting a common loop to a recursive function

Let’s take a look at a common loop for printing reports and see how it can convert
into a recursive function.

• This loop will print out the page number and page headers at each page
break.
• We will assume that the report lines are grouped by some numeric criteria
and we will pretend there is some total we are keeping track of for these
groups.
• At the end of each grouping, we will print out the totals for that group.

For demonstration purposes, we’ve left out all of the subordinate functions,
assuming that they exist and that they perform as expected. Here is the code for our
report printer:

Listing 10. Report-printing program using a normal loop

void print_report(struct report_line report_lines, int num_lines)
{
int num_lines_this_page = 0;
int page_number = 1;
int current_line; / iterates through the lines /
int current_group = 0; / tells which grouping we are in /
int previous_group = 0; / tells which grouping was here on the last loop /
int group_total = 0; / saves totals for printout at the end of the grouping */

print_headings(page_number);
 for(current_line = 0; current_line < num_lines; current_line++)
{
num_lines_this_page++;
if(num_lines_this_page == LINES_PER_PAGE)
{
page_number++;
page_break();
print_headings(page_number);
}

current_group = get_group(report_lines[current_line]);
if(current_group != previous_group)
{
print_totals_for_group(group_total);
group_total = 0;
}

print_line(report_lines[current_line]);

group_total += get_line_amount(report_lines[current_line]);
}
}
Show more

Several bugs have been intentionally left in the program. See if you can spot them.
Because we are continually modifying state variables, it is difficult to see whether
or not at any given moment they are correct. Here is the same program done
recursively:

Listing 11. Report-printing program using recursion

void print_report(struct report_line report_lines, int num_lines)
{
int num_lines_this_page = 0;
int page_number = 1;
int current_line; / iterates through the lines /
int current_group = 0; / tells which grouping we are in /
int previous_group = 0; / tells which grouping was here on the last loop /
int group_total = 0; / saves totals for printout at the end of the grouping /

/ initialize /
print_headings(page_number);

/ Seed the values /

print_report_i(report_lines, 0, 1, 1, 0, 0, num_lines);
}

void print_report_i(struct report_line report_lines, / our structure /

int current_line, / current index into structure /
int num_lines_this_page, / number of lines we've filled this page /
int page_number,
int previous_group, / used to know when to print totals /
int group_total, / current aggregated total /
 int num_lines) / the total number of lines in the structure /
{
if(current_line == num_lines)
{
return;
}
else
{
if(num_lines_this_page == LINES_PER_PAGE)
{
page_break();
print_headings(page_number + 1);
print_report_i(
report_lines,
current_line,
1,
page_number + 1,
previous_group,
group_total,
num_lines);
}
else
{
int current_group = get_group(report_lines[current_line]);
if(current_group != previous_group && previous_group != 0)
{
print_totals_for_group(group_total);
 print_report_i(
report_lines,
current_line,
num_lines_this_page + 1,
page_number,
current_group,
0,
num_lines);
}
else
{
print_line(report_lines[current_line]);
print_report_i(
report_lines,
current_line + 1,
num_lines_this_page + 1,
page_number,
current_group,
group_total + get_line_amount(report_lines[current_line]),
num_lines);

2. Backtracking Algorithms
Backtracking is an algorithmic technique where the goal is to get all solutions to a
problem using the brute force approach. It consists of building a set of all the
solutions incrementally. Since a problem would have constraints, the solutions that
fail to satisfy them will be removed.
- A backtracking algorithm is a problem-solving algorithm that uses a brute
force approach for finding the desired output. The Brute force approach tries
out all the possible solutions and chooses the desired/best solutions.
- Backtracking is a general algorithm for finding solutions to some
computational problems, notably constraint satisfaction problems that
incrementally builds candidates to the solutions, and abandons a candidate
("backtracks") as soon as it determines that the candidate cannot possibly be
completed to a valid solution.

Backtracking is an algorithmic-technique for solving problems recursively by

trying to build a solution incrementally, one piece at a time, removing those
solutions that fail to satisfy the constraints of the problem at any point of time (by
time, here, is referred to the time elapsed till reaching any level of the search tree).

According to the wiki definition,

Backtracking can be defined as a general algorithmic technique that considers se

arching every possible combination in order to solve a computational problem.

There are three types of problems in backtracking –

1. Decision Problem – In this, we search for a feasible solution.

2. Optimization Problem – In this, we search for the best solution.
3. Enumeration Problem – In this, we find all feasible solutions.

How to determine if a problem can be solved using Backtracking?

Generally, every constraint satisfaction problem which has clear and well-defined
constraints on any objective solution, that incrementally builds candidate to the
solution and abandons a candidate (“backtracks”) as soon as it determines that the
candidate cannot possibly be completed to a valid solution, can be solved by
Backtracking. However, most of the problems that are discussed, can be solved
using other known algorithms like Dynamic Programming or Greedy
Algorithms in logarithmic, linear, linear-logarithmic time complexity in order of
input size, and therefore, outshine the backtracking algorithm in every respect
(since backtracking algorithms are generally exponential in both time and space).
However, a few problems still remain, that only have backtracking algorithms to
solve them until now.
Consider a situation that you have three boxes in front of you and only one of them
has a gold coin in it but you do not know which one. So, in order to get the coin,
you will have to open all of the boxes one by one. You will first check the first box,
if it does not contain the coin, you will have to close it and check the second box
and so on until you find the coin. This is what backtracking is, that is solving all
sub-problems one by one in order to reach the best possible solution.

Consider the below example to understand the Backtracking approach more

formally,

Given an instance of any computational problem and data corresponding to

the instance, all the constraints that need to be satisfied in order to solve the
problem are represented by C. A backtracking algorithm will then work as
follows:

The Algorithm begins to build up a solution, starting with an empty solution:

set . S = {}
1. Add to the first move that is still left (All possible moves are added to one
by one). This now creates a new sub-tree in the search tree of the algorithm.
2. Check if S + satisfies each of the constraints in C
• If Yes, then the sub-tree S is “eligible” to add more “children”.
• Else, the entire sub-tree is useless, so recurs back to step 1 using
argument S
3. In the event of “eligibility” of the newly formed sub-tree , recurs back to step
1, using argument S + s.
4. If the check for S + s returns that it is a solution for the entire data D. Output
and terminate the program.
If not, then return that no solution is possible with the current and hence
discard it.
Difference between Recursion and Backtracking:
In recursion, the function calls itself until it reaches a base case. In backtracking,
we use recursion to explore all the possibilities until we get the best result for the
problem.

Pseudo Code for Backtracking :

1. Recursive backtracking solution.

void findSolutions(n, other params) :

if (found a solution) :

solutionsFound = solutionsFound + 1;

displaySolution();

if (solutionsFound >= solutionTarget) :

[Link](0);
 return

for (val = first to last) :

if (isValid(val, n)) :

applyValue(val, n);

findSolutions(n+1, other params);

removeValue(val, n);

2. Finding whether a solution exists or not

boolean findSolutions(n, other params) :

if (found a solution) :

displaySolution();

return true;

for (val = first to last) :

if (isValid(val, n)) :

applyValue(val, n);

if (findSolutions(n+1, other params))

return true;

removeValue(val, n);

return false;
Let us try to solve a standard Backtracking problem, N-Queen Problem.
The N Queen is the problem of placing N chess queens on an N×N chessboard so
that no two queens attack each other. For example, following is a solution for 4
Queen problem.

The expected output is a binary matrix which has 1s for the blocks where queens
are placed. For example, following is the output matrix for the above 4 queen
solution.

{ 0, 1, 0, 0}

{ 0, 0, 0, 1}

{ 1, 0, 0, 0}

{ 0, 0, 1, 0}

Backtracking Algorithm: The idea is to place queens one by one in different

columns, starting from the leftmost column. When we place a queen in a column,
we check for clashes with already placed queens. In the current column, if we find
a row for which there is no clash, we mark this row and column as part of the
solution. If we do not find such a row due to clashes then we backtrack and return
false.
1) Start in the leftmost column

2) If all queens are placed

return true

3) Try all rows in the current column. Do following for every tried

row.

a) If the queen can be placed safely in this row then mark this

[row, column] as part of the solution and recursively

check if placing queen here leads to a solution.

b) If placing the queen in [row, column] leads to a solution then

return true.

c) If placing queen doesn't lead to a solution then unmark this

[row, column] (Backtrack) and go to step (a) to try other rows.

4) If all rows have been tried and nothing worked, return false to

trigger backtracking.

Divide And Conquer

This technique can be divided into the following three parts:
1. Divide: This involves dividing the problem into smaller sub-problems.
2. Conquer: Solve sub-problems by calling recursively until solved.
3. Combine: Combine the sub-problems to get the final solution of the whole
problem.

The following are some standard algorithms that follow Divide and Conquer
algorithm.

1. Quicksort is a sorting algorithm. The algorithm picks a pivot element and

rearranges the array elements so that all elements smaller than the picked pivot
element move to the left side of the pivot, and all greater elements move to the
right side. Finally, the algorithm recursively sorts the subarrays on the left and
right of the pivot element.
2. Merge Sort is also a sorting algorithm. The algorithm divides the array into two
halves, recursively sorts them, and finally merges the two sorted halves.
3. Closest Pair of Points The problem is to find the closest pair of points in a set
of points in the x-y plane. The problem can be solved in O(n^2) time by
calculating the distances of every pair of points and comparing the distances to
find the minimum. The Divide and Conquer algorithm solves the problem in
O(N log N) time.
4. Strassen’s Algorithm is an efficient algorithm to multiply two matrices. A
simple method to multiply two matrices needs 3 nested loops and is O(n^3).
Strassen’s algorithm multiplies two matrices in O(n^2.8974) time.
5. Cooley–Tukey Fast Fourier Transform (FFT) algorithm is the most
common algorithm for FFT. It is a divide and conquer algorithm which works
in O(N log N) time.
6. Karatsuba algorithm for fast multiplication does the multiplication of two n-
digit numbers in at most
single-digit multiplications in general (and exactly when n is a power of
2). It is, therefore, faster than the classical algorithm, which requires n2 single-digit
products. If n = 210 = 1024, in particular, the exact counts are 3 10 = 59, 049 and
(210)2 = 1, 048, 576, respectively.
What does not qualifies as Divide and Conquer:

Binary Search is a searching algorithm. In each step, the algorithm compares the
input element x with the value of the middle element in the array. If the values
match, return the index of the middle. Otherwise, if x is less than the middle
element, then the algorithm recurs for the left side of the middle element, else
recurs for the right side of the middle element. Contrary to popular belief, this is
not an example of Divide and Conquer because there is only one sub-problem in
each step (Divide and conquer requires that there must be two or more sub-
problems) and hence this is a case of Decrease and Conquer.

Divide And Conquer algorithm :

DAC(a, i, j)

if(small(a, i, j))

return(Solution(a, i, j))

else

m = divide(a, i, j) // f1(n)

b = DAC(a, i, mid) // T(n/2)

c = DAC(a, mid+1, j) // T(n/2)

 d = combine(b, c) // f2(n)

return(d)

Recurrence Relation for DAC algorithm :

This is a recurrence relation for the above program.
O(1) if n is small

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

Example:
To find the maximum and minimum element in a given array.
Input: { 70, 250, 50, 80, 140, 12, 14 }
Output: The minimum number in a given array is : 12
The maximum number in a given array is : 250
Approach: To find the maximum and minimum element from a given array is an
application for divide and conquer. In this problem, we will find the maximum and
minimum elements in a given array. In this problem, we are using a divide and
conquer approach(DAC) which has three steps divide, conquer and combine.

For Maximum:
In this problem, we are using the recursive approach to find maximum where we
will see that only two elements are left and then we can easily using condition i.e.
if(a[index] > a[index+1].)
In a program line a[index] and a[index+1])condition will ensure only two
elements in left.
if(index >= l-2)
{
if(a[index]>a[index+1])
{
// (a[index]
// Now, we can say that the last element will be maximum in a given array.
}
else
{
//(a[index+1]
// Now, we can say that last element will be maximum in a given array.
}
}

In the above condition, we have checked the left side condition to find out the
maximum. Now, we will see the right side condition to find the maximum.
Recursive function to check the right side at the current index of an array.

max = DAC_Max(a, index+1, l);

// Recursive call

Now, we will compare the condition and check the right side at the current index
of a given array.
In the given program, we are going to implement this logic to check the condition
on the right side at the current index.

// Right element will be maximum.

if(a[index]>max)
return a[index];
// max will be maximum element in a given array.
else
return max;
}

For Minimum:
In this problem, we are going to implement the recursive approach to find the
minimum no. in a given array.
int DAC_Min(int a[], int index, int l)
//Recursive call function to find the minimum no. in a given array.
if(index >= l-2)
// to check the condition that there will be two-element in the left
then we can easily find the minimum element in a given array.
{
// here we will check the condition
if(a[index]<a[index+1])
return a[index];
else
return a[index+1];
}

Now, we will check the condition on the right side in a given array.

// Recursive call for the right side in the given array.

min = DAC_Min(a, index+1, l);

Now, we will check the condition to find the minimum on the right side.

// Right element will be minimum

if(a[index]<min)
return a[index];
// Here min will be minimum in a given array.
else
return min;

// C++ code to demonstrate Divide and

// Conquer Algorithm#include<iostream>
# include<iostream>
using namespace std;

// function to find the maximum no.

// in a given array.
int DAC_Max(int arr[], int index, int l)
{
int max;
if(index >= l - 2)
{
if(arr[index] > arr[index + 1])
return arr[index];
else
return arr[index + 1];
}
max = DAC_Max(arr, index + 1, l);
if(arr[index] > max)
 return arr[index];
else
return max;
}

// Function to find the minimum no.

// in a given array
int DAC_Min(int arr[], int index, int l)
{
int min;
if(index >= l - 2)
{
if(arr[index] < arr[index + 1])
return arr[index];
else
return arr[index + 1];
}

min = DAC_Min(arr, index + 1, l);

if(arr[index] < min)
return arr[index];
else
return min;
}

// Driver code
int main()
{
int arr[] = {120, 34, 54, 32, 58, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int max, min;
max = DAC_Max(arr, 0, n);
min = DAC_Min(arr, 0, n);
cout << "Maximum: " << max << endl;
cout << "Minimum: " << min << endl;
return 0;
}

// This code is contributed by probinsah.

Divide and Conquer

In divide and conquer approach, the problem in hand, is divided into smaller sub-
problems and then each problem is solved independently. When we keep on
dividing the subproblems into even smaller sub-problems, we may eventually reach
a stage where no more division is possible. Those "atomic" smallest possible sub-
problem (fractions) are solved. The solution of all sub-problems is finally merged
in order to obtain the solution of an original problem.
Broadly, we can understand divide-and-conquer approach in a three-step process.

Divide/Break

This step involves breaking the problem into smaller sub-problems. Sub-problems
should represent a part of the original problem. This step generally takes a recursive
approach to divide the problem until no sub-problem is further divisible. At this
stage, sub-problems become atomic in nature but still represent some part of the
actual problem.

Conquer/Solve

This step receives a lot of smaller sub-problems to be solved. Generally, at this

level, the problems are considered 'solved' on their own.

Merge/Combine
When the smaller sub-problems are solved, this stage recursively combines them
until they formulate a solution of the original problem. This algorithmic approach
works recursively and conquer & merge steps works so close that they appear as
one.

Examples

The following computer algorithms are based on divide-and-

conquer programming approach −

• Merge Sort
• Quick Sort
• Binary Search
• Strassen's Matrix Multiplication
• Closest pair (points)

There are various ways available to solve any computer problem, but the mentioned
are a good example of divide and conquer approach.

Greedy Algorithms
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next
piece that offers the most obvious and immediate benefit. So the problems where choosing locally
optimal also leads to global solution are best fit for Greedy.

For example consider the Fractional Knapsack Problem. The local optimal strategy is to choose the
item that has maximum value vs weight ratio. This strategy also leads to global optimal solution
because we allowed to take fractions of an item.
Analyzing algorithms
It’s not enough just to write down an algorithm and say ‘Behold!’ We must also
convince our audience (and ourselves!) that the algorithm actually does what it’s
supposed to do, and that it does so efficiently.

Algorithms describe processes that run on real computers with finite resources.
Processes consume two resources: processing time and space or memory.
When run with the same problems or data sets, processes that consume less of these
two resources are of higher quality than processes that consume more, and so are the
corresponding algorithms. In this chapter, we introduce tools for complexity
analysis—for assessing the run-time performance or efficiency of algorithms. We
also apply these tools to search algorithms and sort algorithms.

Goal of the Analysis of Algorithms

The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly
in terms of
running time but also in terms of other factors (e.g., memory, developer effort, etc.)
1.8 What is Running Time Analysis?
It is the process of determining how processing time increases as the size of the
problem (input
size) increases. Input size is the number of elements in the input, and depending on
the problem
type, the input may be of different types. The following are the common types of
inputs.
• Size of an array
• Polynomial degree
• Number of elements in a matrix
• Number of bits in the binary representation of the input
• Vertices and edges in a graph.

Correctness
In some application settings, it is acceptable for programs to behave correctly most
of the time, on all ‘reasonable’ inputs. Not in this class; we require algorithms that
are correct for all possible
inputs. Moreover, we must prove that our algorithms are correct; trusting our
instincts, or trying a few test cases, isn’t good enough. Sometimes correctness is
fairly obvious, especially for algorithms you’ve seen in earlier courses. On the other
hand, ‘obvious’ is all too often a synonym for ‘wrong’. Many of the algorithms we
will discuss in this course will require extra work to prove correct. Correctness
proofs almost always involve induction. We like induction. Induction is our friend.¹²
But before we can formally prove that our algorithm does what it’s supposed to do,
we have to formally state what it’s supposed to do! Algorithmic problems are usually
presented using standard English, in terms of real-world objects, not in terms of
formal mathematical objects. It’s
up to us, the algorithm designers, to restate these problems in terms of mathematical
objects that we can prove things about—numbers, arrays, lists, graphs, trees, and so
on. We must also determine if the problem statement carries any hidden
assumptions, and state those assumptions explicitly. (For example, in the song “n
Bottles of Beer on the Wall”, n is always a positive integer.)
Restating the problem formally is not only required for proofs; it is also one of the
best ways to
really understand what a problem is asking for. The hardest part of answering any
question is figuring out the right way to ask it!
It is important to remember the distinction between a problem and an algorithm. A
problem is a task to perform, like “Compute the square root of x” or “Sort these n
numbers” or “Keep n
algorithms students awake for t minutes”. An algorithm is a set of instructions for
accomplishing
such a task. The same problem may have hundreds of different algorithms; the same
algorithm may solve hundreds of different problems.

Running time
The most common way of ranking different algorithms for the same problem is by
how quickly
they run. Ideally, we want the fastest possible algorithm for any particular problem.
In many application settings, it is acceptable for programs to run efficiently most of
the time, on all ‘reasonable’ inputs. Not in this class; we require algorithms that
always run efficiently, even in the worst case.
But how do we measure running time? As a specific example, how long does it take
to sing the song BottlesOfBeer(n)? This is obviously a function of the input value n,
but it also depends on how quickly you can sing. Some singers might take ten
seconds to sing a verse; others might take twenty. Technology widens the
possibilities even further. Dictating the song over a telegraph using Morse code
might take a full minute per verse. Downloading an mp3 over the Web might take a
tenth of a second per verse. Duplicating the mp3 in a computer’s main memory might
take only a few microseconds per verse.

Measuring the Efficiency of Algorithms

Some algorithms consume an amount of time or memory that is below a threshold
of tolerance. For example, most users are happy with any algorithm that loads a file
in less than one second. For such users, any algorithm that meets this requirement is
as good as any other. Other algorithms take an amount of time that is totally
impractical (say, thousands of years) with large data sets. We can’t use these
algorithms, and instead need to find others, if they exist, that perform better.
When choosing algorithms, we often have to settle for a space/time tradeoff. An
algorithm can be designed to gain faster run times at the cost of using extra space
(memory), or the other way around. Some users might be willing to pay for more
memory to get a faster algorithm, whereas others would rather settle for a slower
algorithm that economizes on memory. Memory is now quite inexpensive for
desktop and laptop computers, but not yet for miniature devices.
In any case, because efficiency is a desirable feature of algorithms, it is important to
pay attention to the potential of some algorithms for poor performance. In this
section, we consider several ways to measure the efficiency of algorithms.

Measuring the Run Time of an Algorithm

One way to measure the time cost of an algorithm is to use the computer’s clock to
obtain an actual run time. This process, called benchmarking or profiling, starts by
determining the time for several different data sets of the same size and then
calculates the average time. Next, similar data are gathered for larger and larger data
sets. After several such tests, enough data are available to predict how the algorithm
will behave for a data set of any size.
Consider a simple, if unrealistic, example. The following program implements an
algorithm that counts from 1 to a given number. Thus, the problem size is the
number. We start with the number 10,000,000, time the algorithm, and output the
running time to the terminal window. We then double the size of this

Algorithm Analysis

Efficiency of an algorithm can be analyzed at two different stages, before

implementation and after implementation. They are the following −
1. A Priori Analysis − This is a theoretical analysis of an algorithm. Efficiency
of an algorithm is measured by assuming that all other factors, for example,
processor speed, are constant and have no effect on the implementation.

2. A Posterior Analysis − This is an empirical analysis of an algorithm. The

selected algorithm is implemented using programming language. This is then
executed on target computer machine. In this analysis, actual statistics like
running time and space required are collected.

We shall learn about a priori algorithm analysis. Algorithm analysis deals with the
execution or running time of various operations involved. The running time of an
operation can be defined as the number of computer instructions executed per
operation.
Algorithm Complexity
Suppose X is an algorithm and n is the size of input data, the time and space used by
the algorithm X are the two main factors, which decide the efficiency of X.
- Time Factor – Time is measured by counting the number of key operations
such as comparisons in the sorting algorithm.
- Space Factor − Space is measured by counting the maximum memory space
required by the algorithm.
 There are different types of time complexities, so let's check the most basic ones.

• Constant Time Complexity: O(1) ...

• Linear Time Complexity: O(n) ...
• Logarithmic Time Complexity: O(log n) ...
• Quadratic Time Complexity: O(n²) ...
• Exponential Time Complexity: O(2^n)

Complexity of algorithms
The complexity of an algorithm f(n) gives the running time and/or the storage space
required by the algorithm in terms of n as the size of input data.

Space Complexity
Space complexity of an algorithm represents the amount of memory space required
by the algorithm in its life cycle. The space required by an algorithm is equal to the
sum of the following two components –
- A fixed part, that is, a space required to store certain data and variables, that
are independent of the size of the problem. For example, simple variables and
constants used, program size, etc.
- A variable part is a space required by variables, whose size depends on the
size of the problem. For example, dynamic memory allocation, recursion stack
space, etc.
Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed
part and S(I) is the variable part of the algorithm, which depends on instance
characteristic I

Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop

Here we have three variables A, B, and C and one constant. Hence S(P) = 1+3. Now,
space depends on data types of given variables and constant types and it will be
multiplied accordingly.

Time Complexity

Time complexity of an algorithm represents the amount of time required by the

algorithm to run to completion. Time requirements can be defined as a numerical
function T(n), where T(n) can be measured as the number of steps, provided each
step consumes constant time.

For example, addition of two n-bit integers takes n steps. Consequently, the total
computational time is T(n) = c*n, where c is the time taken for the addition of two
bits. Here, we observe that T(n) grows linearly as the input size increases.

Example
What is time complexity of fun()?

int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}

(A) O(n^2)
(B) O(nLogn)
(C) O(n)
(D) O(nLognLogn)

Answer: (C)

Explanation: For a input integer n, the innermost statement of fun() is executed

following times.
n + n/2 + n/4 + … 1

So time complexity T(n) can be written as

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

The value of count is also n + n/2 + n/4 + .. + 1

Example:

What is the time complexity of the following recursive function:

int DoSomething (int n)

if (n <= 2)

return 1;

else

return (DoSomething (floor(sqrt(n))) + n);

(A) (n)
(B) (nlogn)
(C) (logn)
(D) (loglogn)
(A) A
(B) B
(C) C
(D) D
Answer: (D)

Explanation: Recursive relation for the DoSomething() is

T(n) = T( ) + C1 if n > 2

We have ignored the floor() part as it doesn’t matter here if it’s a floor or ceiling.

Let n = 2^m, T(n) = T(2^m)

Let T(2^m) = S(m)

From the above two, T(n) = S(m)

S(m) = S(m/2) + C1 /* This is simply binary search recursion*/

S(m) = O(logm)

= O(loglogn) /* Since n = 2^m */

Now, let us go back to the original recursive function T(n)

T(n) = S(m)

= O(LogLogn)

Asymptotic Analysis
Asymptotic analysis of an algorithm refers to defining the mathematical
boundation/framing of its run-time performance. Using asymptotic analysis, we can
very well conclude the best case, average case, and worst case scenario of an
algorithm. Asymptotic analysis is input bound i.e., if there's no input to the
algorithm, it is concluded to work in a constant time. Other than the "input" all other
factors are considered constant.

Asymptotic analysis refers to computing the running time of any operation in

mathematical units of computation. For example, the running time of one operation
is computed as f(n) and may be for another operation it is computed as g(n2). This
means the first operation running time will increase linearly with the increase in n
and the running time of the second operation will increase exponentially when n
increases. Similarly, the running time of both operations will be nearly the same if
n is significantly small.
Usually, the time required by an algorithm falls under three types –
- Best Case − Minimum time required for program execution.
- Average Case − Average time required for program execution.
- Worst Case − Maximum time required for program execution.

Asymptotic Notations
Following are the commonly used asymptotic notations to calculate the running time
complexity of an algorithm.
- Ο Notation
- Ω Notation
- θ Notation

Big Oh Notation, Ο
The notation Ο(n) is the formal way to express the upper bound of an algorithm's
running time. It measures the worst case time complexity or the longest amount of
time an algorithm can possibly take to complete.

For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound of an algorithm's
running time. It measures the best case time complexity or the best amount of time
an algorithm can possibly take to complete.
For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

Theta Notation, θ
The notation θ(n) is the formal way to express both the lower bound and the upper
bound of an algorithm's running time. It is represented as follows −

θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }
Common Asymptotic Notations
Following is a list of some common asymptotic notations:

Constant - Ο(1)
Logarithmic - Ο(log n)
linear - Ο(n)
nlogn - Ο(n log n)
quadratic - O(n2)
cubic - O(n3)
Polynomial - nΟ(1)
exponential 2Ο(n)

The Big-O! Time complexity with examples

The very first thing that a good developer considers while choosing between different
algorithms is how much time will it take to run and how much space will it need. In
this article we are going to talk about why considering time complexity is important
and also what are some common time complexities.

Why running time is so important?

Take an example of Google maps, you would want the shortest path from A to B as
fast as possible. Or in case of Data Analysis, you would want the analysis to be done
as fast as possible. So, to get desired results from the algorithm in optimum amount
of time, we take time complexity into consideration.

How to measure time complexity?

Do we measure absolute time?

No, we consider number of steps in algorithm and input size.

Therefore, time complexity is a simplified mathematical way of analyzing how long

an algorithm with a given number of inputs (n) will take to complete its task. The
inputs can be of any sizes but, usually we are interested in large input sizes, so we
make some approximations i.e. we only consider the factor in our expression that has
the greatest impact while ’n’ increases. This is called asymptotic analysis.

There are three types of asymptotic notations used to calculate the running time
complexity of an algorithm:

1) Big-O

2) Big Omega

3) Big theta

Big Omega notation (Ω):

It describes the limiting behavior of a function, when the argument tends towards a
particular value or infinity. It tells the lower bound of an algorithm’s running time. It
measure’s the best case or best amount of time an algorithm can possibly take to
complete.
For example: We have an algorithm that has Ω(n²) running time complexity, then it
is also true that the algorithm has an Ω(n) or Ω(log n) or Ω(1) time complexity.

Big Theta notation (θ):

It describes the limiting behavior of a function, when the argument tends towards a
particular value or infinity. It tells both the lower bound and the upper bound of an
algorithm’s running time.

Big-O notation:

It describes the limiting behavior of a function, when the argument tends towards a
particular value or infinity. It tells the upper bound of an algorithm’s running time. It
measure’s the worst case or the longest amount of time an algorithm can possibly
take to complete.

For example: We have an algorithm that has O(n²) as time complexity, then it is also
true that the algorithm has O(n³) or O(n⁴) or O(n⁵) time complexity.

We will be focusing on Big-O notation in this article. We have already discussed

what a Big-O notation is. Now let us discuss what are the common time complexities
described in Big-O notation.
The above table shows the most common time complexities expressed using Big-O
notation. Let’s go through each one of these common time complexities.

1) Constant Time [O(1)]:

When the algorithm doesn’t depend on the input size then it is said to have a constant
time complexity.

For example, when we have to swap two numbers

function swap(a, b):
temp = a
a=b
b = temp

Other example can be when we have to determine whether the number is odd or even.
For all these examples the time complexity is O(1) as it is independent of input size.

2) Logarithmic Time [O(log n)]:`

When the size of input is reduced in each step then the algorithm is said to have
Logarithmic time complexity. The common example for logarithmic time complexity
is binary search. As we know binary search tree is a sorted or ordered tree. The left
node is always a lesser number than the right node.

Let us take an example of binary search where we need to find the position of an
element in sorted list.
def bin_search(data, value): n = len(data)
#get length of list
left = 0
#initiate left node
right = n – 1
#make right node as n-1 while left <= right:
#when left node <= to right node
mid=(left + right)//2 #divide in two equal parts
if value < data[mid]: #if value less than middle number
right = mid – 1 #then mid–1value in right node
 elif value > data[mid]: #if value greater than middle number
left = mid + 1 #then left node is mid+1
else:
return mid
#else return middleif __name__ == ‘__main__’:
data = [10, 20, 30, 40, 50, 60, 70, 80, 90]
print(bin_search(data, 8))

Here you can see in the code that we are dividing the input size at each step in two
parts, hence we can conclude that the time complexity here is O(log n).

3) Linear Time [O(n)]:

When the time complexity increases linearly with the input size then the algorithm is
supposed to have a Linear time complexity. Consider that we have an algorithm, and
we are calculating the time it takes to sort items.

Number of items to be sorted

As you can see in the above table, the relation between input size and the time taken
is linear, hence we can say that above algorithm has a Linear time complexity.

For example, consider an unsorted list and we want to find out the maximum number
in the list
Numbers = [10,20,300,40.5,50]
maximum = Numbers[0]
for num in Numbers:
if num > maximum:
maximum = num
print(maximum)

In this example we need to look through all the values of list and check whether the
number is greater than the previous number which is stored in the variable
‘maximum’. Hence, the searching through each value in list makes it a time
complexity of O(n), as you are repeating the same action for each number using ‘for’
loop. And inside the for loop it is a checking whether a condition is true or not only
once, hence the time complexity is O(1). Therefore, the overall time complexity
becomes O(n).

4) Quasilinear Time [O(n log n)]:

When each operation in input data have a logarithm time complexity then the
algorithm is said to have quasilinear time complexity.

You can compare this with Linear time complexity, just like in linear complexity
where each input had O(1) time complexity resulting in O(n) time complexity for ’n’
inputs. Similarly here, each input has O(log n) and there are such ’n’ inputs hence the
resulting time complexity is O(n log n).

Quasilinear time complexity is common is sorting algorithms such as mergesort,

quicksort and heapsort.

5) Quadratic Time [O(n²)]:

When the algorithm performs linear operation having O(n) time complexity for each
value in input data, which has ’n’ inputs, then it is said to have a quadratic time
complexity.

For example, we can say whenever there is a nested ‘for’ loop the time complexity is
going to be quadratic time complexity. Because we are iterating through all the values
for each value in the list making it O(n) * O(n) i.e. O(n²) time complexity.
for i in list:
for j in list:
print(i, j)

Few examples of quadratic time complexity are bubble sort, insertion sort, etc.

6) Exponential Time [O(c^n)]:

In this ‘c’ is any constant. Let’s consider c=2 for our article. Therefore, the time
complexity becomes O(2^n).

When the time required by the algorithm doubles then it is said to have exponential
time complexity.

Some of the examples for exponential time complexity are calculating Fibonacci
numbers, solving traveling salesman problem with dynamic programming, etc.

For calculating Fibonacci numbers, we use recursive function, which means that the
function calls itself in the function. Hence the time complexity depends on how many
times does the function calls itself and also on the time complexity of function.
def fibonacci(n):
if n <=1
return n
return Fibonacci(n-1) + Fibonacci(n-2) #function calls itself

7) Factorial [O(n!)]:
When the algorithm grows in a factorial way based on the input size, we can say that
the algorithm has factorial time complexity.

Simple example for this can be finding the factorial of given number.
def factorial(n):
for i in range(n):
print(n)
factorial(n-1)

How to analyze algorithms using Big-O notation?

Now, while analyzing time complexity of an algorithm we need to understand three

cases: best-case, worst-case and average-case.

To understand these cases let us take an example of a one-dimensional array of

integers [12, 6, 2, 8, -5, 22, 0] and our task is to search a specified number in the
given array.

The best case in this example would be when the number that we have to search is
the first number in the array i.e. 12. The number would be found out in one iteration
because the number is at an index 0 hence it becomes the best-case scenario, as it
requires least amount of time to search for number in the array, resulting in giving
optimum time complexity of O(1).

The worst case in the above-mentioned example would be when the number to be
searched is at the end of the array i.e. if we are searching for number 0 in the given
example.
Here the number zero is at an index 6 and we have to traverse through the whole array
to find it. Therefore, the algorithm takes the longest time to search for a number in
the array, resulting in increasing the time complexity. O(n) becomes the time
complexity.

There can be another worst-case scenario when the number to be searched is not in
the given array.

The average-case here would be when the number to be searched is somewhere in

the middle of the array i.e. in the above example it is 8. Then the algorithm is going
to take average amount of time to search for 8 in the array. In this case the number of
steps taken by algorithm would be n/2 but as we are doing asymptotic analysis, we
consider the time complexity of O(n).

Conclusion

From above observations we can say that algorithms with time complexity such as
O(1), O(log n) and O(n) are considered to be fast. Whereas, algorithms with time
complexity of O(n log n) can also be considered as fast but any time complexity
above O(n log n) such as O(n²), O(c^n) and O(n!) are considered to be slow. Hence
we can say that O(n log n) acts like a threshold, any time complexity above it is
slower than the complexities below it.

Of course, when you try to solve complex problems you will come up with hundred
different ways to solve it. So, the point here is not of ‘right’ or ‘wrong’ but of ‘better’
and ‘worse’. Hence, whenever you write a code take time complexity into
perspective, as it will prove to be beneficial in a long run.
Time and Space Complexity Analysis of Algorithm

Every day we come across many problems and we find one or more than one
solutions to that particular problem. Some solutions may be efficient as compared to
others and some solutions may be less efficient. Generally, we tend to use the most
efficient solution.

For example, while going from your home to your office or school or college, there
can be "n" number of paths. But you choose only one path to go to your destination
i.e. the shortest path.

The same idea we apply in the case of the computational problems or problem-
solving via computer. We have one computational problem and we can design
various solutions i.e. algorithms and we choose the most efficient algorithm out of
those developed algorithms.
Critical Ideas to think!

• What is a computational problem? How we extract relevant detail and

transform a real-life problem into a computational problem?

What is an Algorithm?

In computer science, whenever we want to solve some computational problem then

we define a set of steps that need to be followed to solve that problem. These steps
are collectively known as an algorithm.

For example, you have two integers "a" and "b" and you want to find the sum of
those two number. How will you solve this? One possible solution for the above
problem can be:

• Take two integers as input

• create a variable "sum" to store the sum of two integers

• put the sum of those two variables in the "sum" variable

• return the "sum" variable

//taking two integers as input

int findSum(int a, int b)

int sum; // creating the sum variable

sum = a + b; // storing the sum of a and b

 return sum; // returning the sum variable

In the above example, you will find three things i.e. input, algorithm, and output:

• Input: Input is something for which you need to write an algorithm and
transform it into the desired output. Just like in machines where you give some
raw product and the machine transforms the raw product into some desirable
product. In our example, the input is the two numbers i.e. "a" and "b". Before
writing an algorithm, you should find the data type of input, distribution or
range of input and other relevant details related to it. So critically analyse your
input before writing the solution.

• Algorithm: An algorithm is well-defined steps by step procedure that take

some value or set of values as input and produce some value or set of values
as output. In the above example, we are having three steps to find the sum of
two numbers. So, all three steps are collectively called an algorithm to find
the sum of two numbers.

• Output: Output is the desired result in the problem. For example, if we are
finding the sum of two integers a and b then for every value of a and b it must
produce the correct sum as an output.
What do you mean by a good Algorithm?

There can be many algorithms for a particular problem. So, how will you classify an
algorithm to be good and others to be bad? Let's understand the properties of a good
algorithm:

• Correctness: An algorithm is said to be correct if for every set of input it halts

with the correct output. If you are not getting the correct output for any
particular set of input, then your algorithm is wrong.

• Finiteness: Generally, people ignore this but it is one of the important factors
in algorithm evaluation. The algorithm must always terminate after a finite
number of steps. For example, in the case of recursion and loop, your
algorithm should terminate otherwise you will end up having a stack overflow
and infinite loop scenario respectively.

• Efficiency: An efficient algorithm is always used. By the term efficiency, we

mean to say that:

1. The algorithm should efficiently use the resources available to the system.

2. The computational time (the time taken to generate an output corresponding

to a particular input) should be as less as possible.

3. The memory used by the algorithm should also be as less as possible.

Generally, there is a trade-off between computational time and memory. So,
we need to find if the time is more important than space or vice-versa and then
write the algorithm accordingly.
So, we have seen the three factors that can be used to evaluate an algorithm. Out of
these three factors, the most important one is the efficiency of algorithms. So let's
dive deeper into the efficiency of the algorithm.

Algorithm Efficiency

The efficiency of an algorithm is mainly defined by two factors i.e. space and time.
A good algorithm is one that is taking less time and less space, but this is not possible
all the time. There is a trade-off between time and space. If you want to reduce the
time, then space might increase. Similarly, if you want to reduce the space, then the
time may increase. So, you have to compromise with either space or time. Let's learn
more about space and time complexity of algorithms.

Space Complexity

Space Complexity of an algorithm denotes the total space used or needed by the
algorithm for its working, for various input sizes. For example:

vector<int> myVec(n);

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

cin >> myVec[i];

In the above example, we are creating a vector of size n. So the space complexity of
the above code is in the order of "n" i.e. if n will increase, the space requirement will
also increase accordingly.
Even when you are creating a variable then you need some space for your algorithm
to run. All the space required for the algorithm is collectively called the Space
Complexity of the algorithm.

NOTE: In normal programming, you will be allowed to use 256MB of space for a
particular problem. So, you can't create an array of size more 10^8 because you will
be allowed to use only 256MB. Also, you can't create an array of size more than
10^6 in a function because the maximum space allotted to a function is 4MB. So, to
use an array of more size, you can create a global array.

Time Complexity

The time complexity is the number of operations an algorithm performs to complete

its task with respect to input size (considering that each operation takes the same
amount of time). The algorithm that performs the task in the smallest number of
operations is considered the most efficient one.

Input Size: Input size is defined as total number of elements present in the input.
For a given problem we characterize the input size n appropriately. For example:

Sorting problem: Total number of item to be sorted

Graph Problem: Total number of vertices and edges

Numerical Problem: Total number of bits needed to represent a number

The time taken by an algorithm also depends on the computing speed of the system
that you are using, but we ignore those external factors and we are only concerned
on the number of times a particular statement is being executed with respect to the
input size. Let's say, for executing one statement, the time taken is 1sec, then what
is the time taken for executing n statements, It will take n seconds.

Suppose you are having one problem and you wrote three algorithms for the same
problem. Now, you need to choose one out of those three algorithms. How will you
do that?

• One thing that you can do is just run all the three algorithms on three different
computers, provide same input and find the time taken by all the three
algorithms and choose the one that is taking the least amount of time. Is it ok?
No, all the systems might be using some different processors. So, the
processing speed might vary. So, we can't use this approach to find the most
efficient algorithm.

• Another thing that you can do is run all the three algorithms on the same
computer and try to find the time taken by the algorithm and choose the best.
But here also, you might get wrong results because, at the time of execution
of a program, there are other things that are executing along with your
program, so you might get the wrong time.

NOTE: One thing that is to be noted here is that we are finding the time taken by
different algorithms for the same input because if we change the input then the
efficient algorithm might take more time as compared to the less efficient one
because the input size is different for both algorithms.

So, we have seen that we can't judge an algorithm by calculating the time taken
during its execution in a particular system. We need some standard notation to
analyse the algorithm. We use Asymptotic notation to analyse any algorithm and
based on that we find the most efficient algorithm. Here in Asymptotic notation, we
do not consider the system configuration, rather we consider the order of growth of
the input. We try to find how the time or the space taken by the algorithm will
increase/decrease after increasing/decreasing the input size.

There are three asymptotic notations that are used to represent the time complexity
of an algorithm. They are:

• Θ Notation (theta)

• Big O Notation

• Ω Notation

Before learning about these three asymptotic notation, we should learn about the
best, average, and the worst case of an algorithm.

Best case, Average case, and Worst case

An algorithm can have different time for different inputs. It may take 1 second for
some input and 10 seconds for some other input.

For example: We have one array named "arr" and an integer "k". we need to find if
that integer "k" is present in the array "arr" or not? If the integer is there, then
return 1 other return 0. Try to make an algorithm for this question.

The following information can be extracted from the above question:

• Input: Here our input is an integer array of size "n" and we have one integer
"k" that we need to search for in that array.
 • Output: If the element "k" is found in the array, then we have return 1,
otherwise we have to return 0.

Now, one possible solution for the above problem can be linear search i.e. we will
traverse each and every element of the array and compare that element with "k". If
it is equal to "k" then return 1, otherwise, keep on comparing for more elements in
the array and if you reach at the end of the array and you did not find any element,
then return 0.

/*

* @type of arr: integer array

* @type of n: integer (size of integer array)

* @type of k: integer (integer to be searched)

*/

int searchK(int arr[], int n, int k)

// for-loop to iterate with each element in the array

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

// check if ith element is equal to "k" or not

if (arr[i] == k)
 return 1; // return 1, if you find "k"

return 0; // return 0, if you didn't find "k"

/*

* [Explanation]

* i = 0 ------------> will be executed once

* i < n ------------> will be executed n+1 times

* i++ --------------> will be executed n times

* if(arr[i] == k) --> will be executed n times

* return 1 ---------> will be executed once(if "k" is there in the array)

* return 0 ---------> will be executed once(if "k" is not there in the array)

*/

Each statement in code takes constant time, let's say "C", where "C" is some
constant. So, whenever you declare an integer then it takes constant time when you
change the value of some integer or other variables then it takes constant time, when
you compare two variables then it takes constant time. So, if a statement is taking
"C" amount of time and it is executed "N" times, then it will take C*N amount of
time. Now, think of the following inputs to the above algorithm that we have just
written:

NOTE: Here we assume that each statement is taking 1sec of time to execute.

• If the input array is [1, 2, 3, 4, 5] and you want to find if "1" is present in the
array or not, then the if-condition of the code will be executed 1 time and it
will find that the element 1 is there in the array. So, the if-condition will take
1 second here.

• If the input array is [1, 2, 3, 4, 5] and you want to find if "3" is present in the
array or not, then the if-condition of the code will be executed 3 times and it
will find that the element 3 is there in the array. So, the if-condition will take
3 seconds here.

• If the input array is [1, 2, 3, 4, 5] and you want to find if "6" is present in the
array or not, then the if-condition of the code will be executed 5 times and it
will find that the element 6 is not there in the array and the algorithm will
return 0 in this case. So, the if-condition will take 5 seconds here.

As you can see that for the same input array, we have different time for different
values of "k". So, this can be divided into three cases:

• Best case: This is the lower bound on running time of an algorithm. We must
know the case that causes the minimum number of operations to be executed.
In the above example, our array was [1, 2, 3, 4, 5] and we are finding if "1" is
 present in the array or not. So here, after only one comparison, you will get
that your element is present in the array. So, this is the best case of your
algorithm.

• Average case: We calculate the running time for all possible inputs, sum all
the calculated values and divide the sum by the total number of inputs. We
must know (or predict) distribution of cases.

• Worst case: This is the upper bound on running time of an algorithm. We

must know the case that causes the maximum number of operations to be
executed. In our example, the worst case can be if the given array is [1, 2, 3,
4, 5] and we try to find if element "6" is present in the array or not. Here, the
if-condition of our loop will be executed 5 times and then the algorithm will
give "0" as output.

So, we learned about the best, average, and worst case of an algorithm. Now, let's
get back to the asymptotic notation where we saw that we use three asymptotic
notations to represent the complexity of an algorithm i.e. Θ Notation (theta), Ω
Notation, Big O Notation.

NOTE: In the asymptotic analysis, we generally deal with large input size.

Θ Notation (theta)

The Θ Notation is used to find the average bound of an algorithm i.e. it defines an
upper bound and a lower bound, and your algorithm will lie in between these levels.
So, if a function is g(n), then the theta representation is shown as Θ(g(n)) and the
relation is shown as:
Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0

such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

The above expression can be read as theta of g(n) is defined as set of all the functions
f(n) for which there exists some positive constants c1, c2, and n0 such that c1*g(n)
is less than or equal to f(n) and f(n) is less than or equal to c2*g(n) for all n that is
greater than or equal to n0.

For example:

if f(n) = 2n² + 3n + 1

and g(n) = n²

then for c1 = 2, c2 = 6, and n0 = 1, we can say that f(n) = Θ(n²)

Ω Notation

The Ω notation denotes the lower bound of an algorithm i.e. the time taken by the
algorithm can't be lower than this. In other words, this is the fastest time in which
the algorithm will return a result. It’s the time taken by the algorithm when provided
with its best-case input. So, if a function is g(n), then the omega representation is
shown as Ω(g(n)) and the relation is shown as:

Ω(g(n)) = { f(n): there exist positive constants c and n0

such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

The above expression can be read as omega of g(n) is defined as set of all the
functions f(n) for which there exist some constants c and n0 such that c*g(n) is less
than or equal to f(n), for all n greater than or equal to n0.

if f(n) = 2n² + 3n + 1

and g(n) = n²

then for c = 2 and n0 = 1, we can say that f(n) = Ω(n²)

Big O Notation

The Big O notation defines the upper bound of any algorithm i.e. you algorithm can't
take more time than this time. In other words, we can say that the big O notation
denotes the maximum time taken by an algorithm or the worst-case time complexity
of an algorithm. So, big O notation is the most used notation for the time complexity
of an algorithm. So, if a function is g(n), then the big O representation of g(n) is
shown as O(g(n)) and the relation is shown as:

O(g(n)) = { f(n): there exist positive constants c and n0

such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

The above expression can be read as Big O of g(n) is defined as a set of functions
f(n) for which there exist some constants c and n0 such that f(n) is greater than or
equal to 0 and f(n) is smaller than or equal to c*g(n) for all n greater than or equal
to n0.

if f(n) = 2n² + 3n + 1

and g(n) = n²

then for c = 6 and n0 = 1, we can say that f(n) = O(n²)

Big O notation example of Algorithms

Big O notation is the most used notation to express the time complexity of an
algorithm. In this section of the blog, we will find the big O notation of various
algorithms.

Example 1: Finding the sum of the first n numbers.

In this example, we have to find the sum of first n numbers. For example, if n = 4,
then our output should be 1 + 2 + 3 + 4 = 10. If n = 5, then the ouput should be 1 +
2 + 3 + 4 + 5 = 15. Let's try various solutions to this code and try to compare all
those codes.

O(1) solution

// function taking input "n"

int findSum(int n)

return n * (n+1) / 2; // this will take some constant time c1

In the above code, there is only one statement and we know that a statement takes
constant time for its execution. The basic idea is that if the statement is taking
constant time, then it will take the same amount of time for all the input size and we
denote this as O(1).

O(n) solution
In this solution, we will run a loop from 1 to n and we will add these values to a
variable named "sum".

// function taking input "n"

int findSum(int n)

int sum = 0; // -----------------> it takes some constant time "c1"

for(int i = 1; i <= n; ++i) // --> here the comparision and increment will take
place n times(c2*n) and the creation of i takes place with some constant time

sum = sum + i; // -----------> this statement will be executed n times i.e. c3*n

return sum; // ------------------> it takes some constant time "c4"

/*

* Total time taken = time taken by all the statments to execute

* here in our example we have 3 constant time taking statements i.e. "sum = 0", "i
= 0", and "return sum", so we can add all the constatnts and replacce with some
new constant "c"

* apart from this, we have two statements running n-times i.e. "i < n(in real n+1)"
and "sum = sum + i" i.e. c2*n + c3*n = c0*n

* Total time taken = c0*n + c

*/

The big O notation of the above code is O(c0*n) + O(c), where c and c0 are
constants. So, the overall time complexity can be written as O(n).

O(n²) solution

In this solution, we will increment the value of sum variable "i" times i.e. for i = 1,
the sum variable will be incremented once i.e. sum = 1. For i = 2, the sum variable
will be incremented twice. So, let's see the solution.

// function taking input "n"

int findSum(int n)

int sum = 0; // ---------------------> constant time

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

for(int j = 1; j <= i; ++j)

sum++; // -------------------> it will run [n * (n + 1) / 2]

return sum; // ----------------------> constant time

/*

* Total time taken = time taken by all the statments to execute

* the statement that is being executed most of the time is "sum++" i.e. n * (n + 1) /
2

* So, total complexity will be: c1*n² + c2*n + c3 [c1 is for the constant terms of n²,
c2 is for the constant terms of n, and c3 is for rest of the constant time]

*/

The big O notation of the above algorithm is O(c1*n²) +O( c2*n) + O(c3). Since we
take the higher order of growth in big O. So, our expression will be reduced to O(n²).

So, until now, we saw 3 solutions for the same problem. Now, which algorithm will
you prefer to use when you are finding the sum of first "n" numbers? If your answer
is O(1) solution, then we have one bonus section for you at the end of this blog. We
would prefer the O(1) solution because the time taken by the algorithm will be
constant irrespective of the input size.

Example 2: Searching Algorithm

In this part of the blog, we will find the time complexity of various searching
algorithms like the linear search and the binary search.

Linear Search

In a linear search, we will be having one array and one element is also given to us.
We need to find the index of that element in the array. For example, if our array is
[8, 10, 3, 2, 9] and we want to find the position of "3", then our output should be 2
(0 based indexing). Following is the code for the same:

/*
* @type of arr: integer array

* @type of n: integer(denoting size of arr)

* @type of k: integer(element to be searched)

*/

int linearSearch(int arr[], int n, int k)

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

if(arr[i] == k)

return i;

return -1;

/*

* [Explanation]

* i = 0 ------------> will be executed once

* i < n ------------> will be executed n+1 times

* i++ --------------> will be executed n times

* if(arr[i] == k) --> will be executed n times

* return i ---------> will be executed once(if "k" is there in the array)

* return -1 --------> will be executed once(if "k" is not there in the array)

*/

The worst-case time complexity of linear search is O(n) because in the worst case
the "if(arr[i] == k)" statement will be executed "n" times.

Binary Search

In a binary search, we will be having one sorted array and an element will be given.
We have to find the position of that element in the array. To do so, we follow the
below steps:

1. Divide the whole array into two parts by finding the middle element of the
array.
 2. Find if the middle element is equal to the element "k" that you are searching
for. If it is equal, then return the value.

3. If the middle element is not equal to element "k", then find if the element "k"
is larger than or smaller than the middle element.

4. If the element "k" is larger than the middle element, then we will perform the
binary search in the [mid+1 to n] part of the array and if the element "k" is
smaller than the middle element, then we will perform the binary search in the
[0 to mid-1] part of the array.

5. Again we will repeat from step number 2.

Let write the code for the same:

/*

* @type of arr: integer array

* @type of left: integer(left most index of arr)

* @type of right: integer(right most index of arr)

* @type of k: integer(element to be searched)

* @return type: integer(index of element k(if found), otherwise return -1)

*/

int binarySearch(int arr[], int left, int right, int k)

{
 while (left <= right) {

// finding the middle element

int mid = left + (right - left) / 2;

// Check if k is present at middle

if (arr[mid] == k)

return mid; // if k is found, then return the mid index

// If k greater, ignore the left half of the array

if (arr[mid] < k)

left = mid + 1; // update the left, right will remain same

// If k is smaller, ignore the right half of the array

else

right = mid - 1; // update the right, left will remain same

// if element is not found, then return -1

return -1;

Let's understand the working of the above code with the help of one example.
Finding the Time Complexity of Binary Search

• For finding the element "k", let's say after "ith" iteration, the iteration of
Binary search stops i.e. the size of the array becomes 1. Also, we are reducing
the size of our array by half after every iteration.

• So, during 1st iteration the size of the array is "n", during 2nd iteration the
size of the array is "n/2", during 3rd iteration the size of the array is "(n/2)/2
= n/2²", during 4th iteration the size of the array is "((n/2)/2)/2 = n/2³", and so
on.

• So, after the ith iteration, the size of the array will be n/2^i. Also, after
the ith iteration, the length of the array will become 1. So, the following
relation should hold true:

=> n/2^i = 1

=> n = 2^i
=> log2 (n) = log2 (2^i) [applying log2 both sides]

=> log2 (n) = i * log2 (2)

=> i = log2 (n) [as logn (n) = 1]

So, the worst-case time complexity of Binary Search is log2 (n).

Example 2: Sorting Algorithm

In this part of the blog, we will learn about the time complexity of the various sorting
algorithm. Sorting algorithms are used to sort a given array in ascending or
descending order. So, let's start with the Selection Sort.

Selection Sort

In selection sort, in the first pass, we find the minimum element of the array and put
it in the first place. In the second pass, we find the second smallest element of the
array and put it in the second place and so on.

/*

* @type of arr: integer array

* @type of n: integer(length of arr)

*/

void selectionSort(int arr[], int n)

{
 // move from index 0 to n-1

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

// finding the minimum element

int minIndex = i;

for (int j = i+1; j < n; j++)

if (arr[j] < arr[minIndex])

minIndex = j;

// Swap the found minimum element with the ith element

swap(arr[minIndex], arr[i]);

The worst-case time complexity of Selection Sort is O(n²).

Bubble Sort

In bubble sort, we compare the adjacent elements and put the smallest element before
the largest element. For example, if the two adjacent elements are [4, 1], then the
final output will be [1, 4].
/*

* @type of arr: integer array

* @type of n: integer(length of arr)

*/

void bubbleSort(int arr[], int n)

// move from index 0 to n-1

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

for (int j = 0; j < n-i-1; j++)

if (arr[j] > arr[j+1]) // comparing adjacent elements

swap(arr[j], arr[j+1]); // swapping elements

The worst-case time complexity of Bubble Sort is O(n²).

Insertion Sort

In Insertion sort, we start with the 1st element and check if that element is smaller
than the 0th element. If it is smaller then we put that element at the desired place
otherwise we check for 2nd element. If the 2nd element is smaller than 0th or 1st
element, then we put the 2nd element at the desired place and so on.
/*

* @type of arr: integer array

* @type of n: integer(length of arr)

*/

void insertionSort(int arr[], int n)

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

int key = arr[i]; // select value to be inserted

int j = i - 1; // position where number is to be inserted

// check if previous no. is larger than value to be inserted

while (j >= 0 && arr[j] > key)

arr[j + 1] = arr[j];

j = j - 1;

// changing the value

 arr[j + 1] = key;

The worst-case time complexity of Insertion Sort is O(n²).

Merge Sort

Merger Sort uses Divide and Conquer technique(you will learn more about divide
and conquer in this Data Structure series). The following steps are involved in Merge
Sort:

• Divide the array into two halves by finding the middle element.

• Call the Merge Sort function on the first half and the second half.

• Now, merge the two halves by calling the Merge function.

Here, we will use recursion, so to learn about recursion, you can read from here).

void merge(int* arr, int start, int mid, int end)

int temp[end - start + 1]; // creating temporary array

int i = start, j = mid+1, k = 0;

while(i <= mid && j <= end) // traverse and add smaller of both elements
in temp
{

if(arr[i] <= arr[j])

temp[k] = arr[i];

k += 1; i += 1;

else

temp[k] = arr[j];

k += 1; j += 1;

// add the elements left in the 1st interval

while(i <= mid)

temp[k] = arr[i];

k += 1; i += 1;
 }

// add the elements left in the 2nd interval

while(j <= end)

temp[k] = arr[j];

k += 1; j += 1;

// updating the original array to have the sorted elements

for(i = start; i <= end; i += 1)

arr[i] = temp[i - start]

/*

* @type of arr: integer array

* @type of start: starting index of arr

* @type of end: eningd index of arr

*/

void mergeSort(int *arr, int start, int end)

if(start < end)

int mid = (start + end) / 2; // finding middle element

mergeSort(arr, start, mid); // calling mergeSort for first half

mergeSort(arr, mid+1, end); // calling mergeSort for second half

merge(arr, start, mid, end); // calling merge function to merge the

arrays

The worst-case time complexity of Merge Sort is O(n log(n) ).

The following table shows the best case, average case, and worst-case time
complexity of various sorting algorithms:
-----------------------------------------------------------------------------

|Sorting Algorithm | Best Case | Average Case | Worst Case |

|------------------|------------------|------------------|------------------|

|Selection Sort | Ω(n²) | θ(n²) | O(n²) |

|Bubble Sort | Ω(n) | θ(n²) | O(n²) |

|Insertion Sort | Ω(n) | θ(n²) | O(n²) |

|Merge Sort | Ω(n logn(n)) | θ(n logn(n)) | O(n logn(n)) |

|Quick Sort | Ω(n logn(n)) | θ(n logn(n)) | O(n²) |

|Heap Sort | Ω(n logn(n)) | θ(n logn(n)) | O(n logn(n)) |

|Radix Sort | Ω(nk) | θ(nk) | O(nk) |

|Bucket Sort | Ω(n + k) | θ(n + k) | O(n²) |

-----------------------------------------------------------------------------

Bonus Section :)

So, here is one bonus section for you. This will help you in choosing the best solution
for a particular question that you will be solving on our website.

So, when you solve some coding questions, then you will be given some input
constraints and based on those constraints you have to decide the time complexity
of your algorithm. Generally, a typical computer system executes 10^18 operations
in one second. So, if the time limit for a particular question is one second and you
are trying to execute more than 10^18 instruction per second, then you will get Time
Limit Exceed(TLE) error. So, based on the input size, you should decide the time
complexity of your algorithm. The following table will help you to decide the time
complexity of your algorithm based on the input size:

--------------------------------

|Input Size | Max Complexity |

|-----------|------------------|

|10^18 | O(logn) |

|10^8 | O(n) |

|10^7 | O(nlogn) |

|10^4 | O(n^2) |

|10^2 | O(n^3) |

|9*10 | O(n^4) |

--------------------------------

Use this table to decide the complexity of your code before writing the code for any
problem and get rid of the TLE (thank me by solving questions from here ;))