Definition, Types, Complexity and Examples of Algorithm

An algorithm is a well-defined sequential computational

technique that accepts a value or a collection of values as input
and produces the output(s) needed to solve a problem.
Or we can say that an algorithm is said to be accurate if and only
if it stops with the proper output for each input instance.

NEED OF THE ALGORITHMS :

Algorithms are used to solve problems or automate tasks in a
systematic and efficient manner. They are a set of instructions or
rules that guide the computer or software in performing a
particular task or solving a problem.

There are several reasons why we use algorithms:

Efficiency: Algorithms can perform tasks quickly and

accurately, making them an essential tool for tasks that require a
lot of calculations or data processing.
Consistency: Algorithms are repeatable and produce consistent
results every time they are executed. This is important when
dealing with large amounts of data or complex processes.
Scalability: Algorithms can be scaled up to handle large
datasets or complex problems, which makes them useful for
applications that require processing large volumes of data.
Automation: Algorithms can automate repetitive tasks,
reducing the need for human intervention and freeing up time
for other tasks.
Standardization: Algorithms can be standardized and shared
among different teams or organizations, making it easier for
people to collaborate and share knowledge.
Overall, algorithms are an essential tool for solving problems in
a variety of fields, including computer science, engineering, data
analysis, finance, and many others.
Example:
Consider a box where no one can see what's happening
inside, we say a black box.
We give input to the box and it gives us the output we need
but the procedure that we might need to know behind the
conversion of input to desired output is an ALGORITHM.

An algorithm is independent of the language used. It tells the

programmer the logic used to solve the problem. So, it is a
logical step-by-step procedure that acts as a blueprint to
programmers.

Real-life examples that define the use of algorithms:

Consider a clock. We know the clock is ticking but how does
the manufacturer set those nuts and bolts so that it keeps on
moving every 60 seconds, the min hand should move and every
60 mins, the hour hand should move? So to solve this problem,
there must be an algorithm behind it.
Seen someone cooking your favorite food for you? Is the recipe
necessary for it? Yes, it is necessary as a recipe is a sequential
procedure that turns a raw potato into a chilly potato. This is
what an algorithm is: following a procedure to get the desired
output. Is the sequence necessary to be followed? Yes, the
sequence is the most important thing that has to be followed to
get what we want.

Types of Algorithms:
Sorting algorithms: Bubble Sort, insertion sort, and many
more. These algorithms are used to sort the data in a particular
format.

Searching algorithms: Linear search, binary search, etc. These

algorithms are used in finding a value or record that the user
demands.
Graph Algorithms: It is used to find solutions to problems like
finding the shortest path between cities, and real-life problems
like traveling salesman problems.

Sorting algorithms are algorithms that take a collection of

elements and rearrange them in a specified order (e.g. ascending
or descending). There are many different sorting algorithms,
each with its own strengths and weaknesses. Some of the most
commonly used sorting algorithms include:

Bubble sort: A simple sorting algorithm that repeatedly steps

through the list, compares adjacent elements and swaps them if
they are in the wrong order.
Insertion sort: A simple sorting algorithm that builds up the final
sorted array one item at a time, by comparing each new item to
the items that have already been sorted and inserting it in the
correct position.
Selection sort: A simple sorting algorithm that repeatedly selects
the minimum element from the unsorted part of the array and
moves it to the end of the sorted part.
Merge sort: A divide-and-conquer sorting algorithm that works
by dividing the unsorted list into n sub-lists, sorting each sub-
list, and then merging them back into a single sorted list.
Quick sort: A divide-and-conquer sorting algorithm that works
by selecting a "pivot" element from the array and partitioning
the other elements into two sub-arrays, according to whether
they are less than or greater than the pivot. The sub-arrays are
then sorted recursively.
Each of these algorithms has different time and space
complexities, making some more suitable for certain use cases
than others.
Searching algorithms are algorithms that search for a particular
element or value in a data structure (such as an array or a linked
list). Some of the most commonly used searching algorithms
include:
Linear search: A simple searching algorithm that iterates
through every element of a list until it finds a match.
Binary search: A searching algorithm that works by dividing a
sorted list in half repeatedly, until the desired element is found
or it can be determined that the element is not present.
Jump search: A searching algorithm that works by jumping
ahead by fixed steps in the list, until a suitable candidate is
found, and then performing a linear search in the surrounding
elements.
Interpolation search: A searching algorithm that works by using
information about the range of values in the list to estimate the
position of the desired element and then verifying that it is
indeed present.
Hash table search: A searching algorithm that uses a hash
function to map elements to indices in an array, and then
performs constant-time lookups in the array to find the desired
element.
Each of these algorithms has different time and space
complexities, making some more suitable for certain use cases
than others. The choice of which algorithm to use depends on
the specific requirements of the problem, such as the size of the
data structure, the distribution of values, and the desired time
complexity.
Graph algorithms are a set of algorithms that are used to
process, analyze and understand graph data structures. Graphs
are mathematical structures used to model relationships between
objects, where the objects are represented as vertices (or nodes)
and the relationships between them are represented as edges.
Graph algorithms are used in a variety of applications such as
network analysis, social network analysis, recommendation
systems, and in many other areas where understanding the
relationships between objects is important. Some of the common
graph algorithms include:
Shortest Path algorithms (e.g. Dijkstra's, Bellman-Ford, A*)
Minimum Spanning Tree algorithms (e.g. Kruskal, Prim)
Maximum Flow algorithms (e.g. Ford-Fulkerson, Edmonds-
Karp)
Network Flow algorithms (e.g. Bipartite Matching)
Connectivity algorithms (e.g. Depth-first Search, Breadth-first
Search)
Why do we use algorithms?
Consider two kids, Aman and Rohan, solving the Rubik's Cube.
Aman knows how to solve it in a definite number of steps. On
the other hand, Rohan knows that he will do it but is not aware
of the procedure. Aman solves the cube within 2 minutes
whereas Rohan is still stuck and by the end of the day, he
somehow managed to solve it (might have cheated as the
procedure is necessary).
So the time required to solve with a procedure/algorithm is
much more effective than that without any procedure. Hence the
need for an algorithm is a must.
In terms of designing a solution to an IT problem, computers are
fast but not infinitely fast. The memory may be inexpensive but
not free. So, computing time is therefore a bounded resource and
so is the space in memory. So we should use these resources
wisely and algorithms that are efficient in terms of time and
space will help you do so.
Creating an Algorithm:
Since the algorithm is language-independent, we write the steps
to demonstrate the logic behind the solution to be used for
solving a problem. But before writing an algorithm, keep the
following points in mind:
The algorithm should be clear and unambiguous.
There should be 0 or more well-defined inputs in an algorithm.
An algorithm must produce one or more well-defined outputs
that are equivalent to the desired output. After a specific number
of steps, algorithms must ground to a halt.
Algorithms must stop or end after a finite number of steps.
In an algorithm, step-by-step instructions should be supplied,
and they should be independent of any computer code.
Example: algorithm to multiply 2 numbers and print the result:
Step 1: Start
Step 2: Get the knowledge of input. Here we need 3 variables; a
and b will be the user input and c will hold the result.
Step 3: Declare a, b, c variables.
Step 4: Take input for a and b variable from the user.
Step 5: Know the problem and find the solution using operators,
data structures and logic
We need to multiply a and b variables so we use * operator and
assign the result to c.
That is c <- a * b
Step 6: Check how to give output, Here we need to print the
output. So write print c
Step 7: End
Example 1: Write an algorithm to find the maximum of all the
elements present in the array.
Follow the algorithm approach as below:
Step 1: Start the Program
Step 2: Declare a variable max with the value of the first
element of the array.
Step 3: Compare max with other elements using loop.
Step 4: If max < array element value, change max to new max.
Step 5: If no element is left, return or print max otherwise goto
step 3.
Step 6: End of Solution
Example 2: Write an algorithm to find the average of 3
subjects.
Follow the algorithm approach as below:
Step 1: Start the Program
Step 2: Declare and Read 3 Subject, let's say S1, S2, S3
Step 3: Calculate the sum of all the 3 Subject values and store
result in Sum variable (Sum = S1+S2+S3)
Step 4: Divide Sum by 3 and assign it to Average variable.
(Average = Sum/3)
Step 5: Print the value of Average of 3 Subjects
Step 6: End of Solution
Know about Algorithm Complexity:
Complexity in algorithms refers to the amount of resources
(such as time or memory) required to solve a problem or
perform a task. The most common measure of complexity is
time complexity, which refers to the amount of time an
algorithm takes to produce a result as a function of the size of
the input. Memory complexity refers to the amount of memory
used by an algorithm. Algorithm designers strive to develop
algorithms with the lowest possible time and memory
complexities, since this makes them more efficient and scalable.
The complexity of an algorithm is a function describing the
efficiency of the algorithm in terms of the amount of data the
algorithm must process.
Usually there are natural units for the domain and range of this
function.
An algorithm is analyzed using Time Complexity and Space
Complexity. Writing an efficient algorithm help to consume the
minimum amount of time for processing the logic. For algorithm
A, it is judged on the basis of two parameters for an input of size
n:
Time Complexity: Time taken by the algorithm to solve the
problem. It is measured by calculating the iteration of loops,
number of comparisons etc.
Time complexity is a function describing the amount of time an
algorithm takes in terms of the amount of input to the algorithm.
"Time" can mean the number of memory accesses performed,
the number of comparisons between integers, the number of
times some inner loop is executed, or some other natural unit
related to the amount of real time the algorithm will take.
Space Complexity: Space taken by the algorithm to solve the
problem. It includes space used by necessary input variables and
any extra space (excluding the space taken by inputs) that is
used by the algorithm. For example, if we use a hash table (a
kind of data structure), we need an array to store values so
this is an extra space occupied, hence will count towards the
space complexity of the algorithm. This extra space is known as
Auxiliary Space.
Space complexity is a function describing the amount of
memory(space)an algorithm takes in terms of the amount of
input to the algorithm.
Space complexity is sometimes ignored because the space used
is minimal and/ or obvious, but sometimes it becomes an issue
as time.
.The time complexity of the operations:
The choice of data structure should be based on the time
complexity of the operations that will be performed.
Time complexity is defined in terms of how many times it takes
to run a given algorithm, based on the length of the input.
The time complexity of an algorithm is the amount of time it
takes for each statement to complete. It is highly dependent on
the size of the processed data.
For example, if you need to perform searches frequently, you
should use a binary search tree.
.The space complexity of the operations:
The choice of data structure should be based on the space
complexity of the operations that will be performed.
The amount of memory used by a program to execute it is
represented by its space complexity.
Because a program requires memory to store input data and
temporal values while running , the space complexity is
auxiliary and input space.
For example, if you need to store a lot of data, you should use an
array.
cases in complexities:
There are two commonly studied cases of complexity in
algorithms:
1.Best case complexity: The best-case scenario for an algorithm
is the scenario in which the algorithm performs the minimum
amount of work (e.g. takes the shortest amount of time, uses the
least amount of memory, etc.).
2.Worst case complexity: The worst-case scenario for an
algorithm is the scenario in which the algorithm performs the
maximum amount of work (e.g. takes the longest amount of
time, uses the most amount of memory, etc.).
In analyzing the complexity of an algorithm, it is often more
informative to study the worst-case scenario, as this gives a
guaranteed upper bound on the performance of the algorithm.
Best-case scenario analysis is sometimes performed, but is
generally less important as it provides a lower bound that is
often trivial to achieve.
Advantages of Algorithms
Easy to understand: Since it is a stepwise representation of a
solution to a given problem, it is easy to understand.
Language Independent: It is not dependent on any programming
language, so it can easily be understood by anyone.
Debug / Error Finding: Every step is independent / in a flow so
it will be easy to spot and fix the error.
Sub-Problems: It is written in a flow so now the programmer
can divide the tasks which makes them easier to code.
Disadvantages of Algorithms
Creating efficient algorithms is time-consuming and requires
good logical skills.
Nasty to show branching and looping in algorithms.