An algorithm is a finite set of instructions, those if followed, accomplishes a particular task.

It is
not language specific, we can use any language and symbols to represent instructions. It can also
be defined as 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. An algorithm
is said to be accurate if and only if it stops with the proper output for each input instance.
Algorithm complexity is a measure which evaluates the order of the count of operations,
performed by a given or algorithm as a function of the size of the input data. To put this simpler,
complexity is a rough approximation of the number of steps necessary to execute an algorithm.
When we evaluate complexity we speak of order of operation count, not of their exact count. For
example, if we have an order of N2 operations to process N elements, then N 2/2 and 3*N2 are of
one and the same quadratic order.
Algorithmic Complexity is a measure of how long an algorithm would take to complete given an
input of size n. If an algorithm needs to scale, it should calculate the output within a finite and
practical time bound, even for large values of n. For this reason, complexity is determined
asymptotically as n approaches infinity. While complexity is generally in terms of time,
sometimes complexity is also evaluated in terms of space, which interprets the algorithm's
memory requirements.
The Space Complexity of an algorithm is defined as a measure of the amount of space or
memory occupied by an algorithm to execute as a function of the length of the input. At the same
time, the Time Complexity of an algorithm is defined as a measure of the amount of time taken
by an algorithm in order to execute as a function of the length of the input. Now that we know
the significance of Time Complexity, it is time to understand what time complexity is and how
we can evaluate it.
In order to explain, Time Complexity measures the time taken in order to execute each statement
of code in an algorithm. In case a statement is set to run repeatedly, then the number of times that
statement gets executed is equal to N multiplied by the time required for the execution of that
function each time.
Algorithm complexity is commonly represented with the O(f) notation, also known as
asymptotic notation or “Big O notation”, where f is the function of the size of the input data. The
asymptotic computational complexity O(f) measures the order of the consumed resources (CPU
time, memory, etc.) by certain algorithm expressed as function of the input data size.
Complexity can be constant, logarithmic, linear, n*log(n), quadratic, cubic, exponential, etc. This
is respectively the order of constant, logarithmic, linear and so on, number of steps, are executed
to solve a given problem. For simplicity, sometime instead of “algorithms complexity” or just
“complexity” we use the term “running time”
Algorithmic Complexity: This measures the resources (time and space) an algorithm requires to
complete, based on the size of the input.
Time Complexity: Describes how long an algorithm takes to run as the input size grows.
Space Complexity: Describes how much memory an algorithm requires as the input size grows.
Big O Notation: A common way to represent algorithmic complexity, focusing on the dominant
term that determines the growth rate of the algorithm.
Examples of Time Complexities:
O(1) (Constant Time): Algorithm's execution time remains the same regardless of the input size.
O(logn) (Logarithmic Time): Execution time grows proportionally to the logarithm of the input
size.
O(n) (Linear Time): Execution time grows proportionally to the input size.
O(nlog n) (Log-linear Time): Execution time grows proportionally to n multiplied by the
logarithm of n.
O(n2) (Quadratic Time): Execution time grows proportionally to the square of the input size.

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.

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
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.
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:
[Link] 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.).
[Link] 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.
Complexity analysis is defined as a technique to characterise the time taken by an algorithm with
respect to input size (independent from the machine, language and compiler). It is used for
evaluating the variations of execution time on different algorithms.
What is the need for Complexity Analysis?
Complexity Analysis determines the amount of time and space resources required to execute it.
It is used for comparing different algorithms on different input sizes.
Complexity helps to determine the difficulty of a problem.
often measured by how much time and space (memory) it takes to solve a particular problem
Asymptotic Notations in Complexity Analysis:
1. Big O Notation
Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it
gives the worst-case complexity of an algorithm. By using big O- notation, we can
asymptotically limit the expansion of a running time to a range of constant factors above and
below. It is a model for quantifying algorithm performance.

Analysis of algorithms
Algorithm analysis is an important part of computational complexities. The complexity theory
provides the theoretical estimates for the resources needed by an algorithm to solve any
computational task. Analysis of the algorithm is the process of analyzing the problem-solving
capability of the algorithm in terms of the time and size required (the size of memory for storage
while implementation). However, the main concern of the analysis of the algorithm is the
required time or performance.
Complexities of an Algorithm
The complexity of an algorithm computes the amount of time and spaces required by an
algorithm for an input of size (n). The complexity of an algorithm can be divided into two types.
The time complexity and the space complexity.

Time Complexity of an Algorithm

The time complexity is defined as the process of determining a formula for total time required
towards the execution of that algorithm. This calculation is totally independent of
implementation and programming language.

Space Complexity of an Algorithm

Space complexity is defining as the process of defining a formula for prediction of how much
memory space is required for the successful execution of the algorithm. The memory space is
generally considered as the primary memory.

Complexity of an Algorithm
The Space and Time complexity of an algorithm can be utilized in order to determine its
effectiveness. While most of us know that there are various methods for addressing any problem
in programming, understanding how an algorithm works effectively and efficiently can add value
to your programming. In order to determine the efficacy of a program or algorithm,
understanding the way of evaluating them with the help of Time and Space Complexity can help
the program perform optimally under certain conditions. Consequently, we become more
efficient programmers.

Understanding the Algorithmic Complexity

Algorithmic Complexity is a measure of how long an algorithm would take to complete given an
input of size n. If an algorithm needs to scale, it should calculate the output within a finite and
practical time bound, even for large values of n. For this reason, complexity is determined
asymptotically as n approaches infinity. While complexity is generally in terms of time,
sometimes complexity is also evaluated in terms of space, which interprets the algorithm's
memory requirements.
Analysis of the complexity of an algorithm is practical when comparing algorithms or seeking
improvements. Algorithmic complexity lies within a branch of theoretical computer science
called computational complexity theory. It is significant to state that we're concerned about the
order of the complexity of an algorithm, not the actual execution time in terms of milliseconds.
Algorithmic Complexity is also known as Complexity or Running Time.

What is the significance of Time Complexity?

First of all, let us understand what defines an algorithm.
In Computer Programming, an Algorithm is a finite sequence of well-defined instructions,
typically executed in a computer, in order to solve a class of problems or perform a common
activity. On the basis of the definition, there must be a sequence of defined instructions that are
required to be given to the computer to execute an algorithm or perform the same activity.
Moreover, with choices available to select any of the available programming languages, the
instructions can take any form of syntax and the performance boundaries of the selected
programming language. We also specified the algorithm to be performed in a computer, which
leads to the succeeding deviation in terms of the operating system, processor, hardware, and
many more that are utilized, which can also influence the manner in which an algorithm can be
performed.
Now that we know various factors can manipulate the result of an algorithm being executed, it is
wise to understand how efficiently such programs are utilized in the performance of an activity.
To assess this, we must calculate both the Space and Time complexity of an Algorithm.
The Space Complexity of an algorithm is defined as a measure of the amount of space or
memory occupied by an algorithm to execute as a function of the length of the input. At the same
time, the Time Complexity of an algorithm is defined as a measure of the amount of time taken
by an algorithm in order to execute as a function of the length of the input. Now that we know
the significance of Time Complexity, it is time to understand what time complexity is and how
we can evaluate it.
In order to explain, Time Complexity measures the time taken in order to execute each statement
of code in an algorithm. In case a statement is set to run repeatedly, then the number of times that
statement gets executed is equal to N multiplied by the time required for the execution of that
function each time.
print("This is a simple statement.")
print("\nOutput:\n")
print("This is a simple statement.")
print("\nCode 2:\n")
for i in range(10):
print("This is a simple statement.")
The code will display the statement once, followed by the output label, and then print the
statement 10 times in the second part
This is a simple statement.
Output:
This is a simple statement.
Code 2:
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
This is a simple statement.
The first algorithm is defined to print the statement only once. The time taken for the execution
of this algorithm is shown as 0 nanoseconds. The second algorithm is defined to print the same
statement; however, this time, it is set to execute the same statement in the FOR loop 10 times.
In the second algorithm, the time taken for the execution of both lines of code - FOR loop and
print statement, is 5 milliseconds. Moreover, the time taken increases as the N value increases
since the statement is going to get executed for N times.
By now, we could have concluded that whenever an algorithm utilizes statements that get
executed only once, it will always need the same amount of time. Then when the statement is in
loop condition, the time required increases on the basis of the number of times the loop is set to
execute. Moreover, whenever an algorithm has a combination of single executed statements and
loop statements or with nested loop statements, the time increases proportionally on the basis of
the number of times each statement gets executed.
Now that we understand the overall concept of time complexity and its significance, it is time to
understand how we can determine the relationship between the input and time, given a statement
in an algorithm. In order to define the relationship between the two, we are going to learn about
Big-O Notation.
What is Big-O Notation?
In theoretical terms, Big-O notation is utilized for the examination of the
performance/complexity of an algorithm.
Big-O notation examines the upper bound of the performance of an algorithm, i.e., the worst-
case scenario.
Big-O notation also considers asymptotic algorithm behavior, which implies the performance of
the method when the amount of the input becomes extremely big.
The computational complexity asymptote, O(f), measures the order of the employed resources on
the basis of the magnitude of the input data (CPU time, RAM, and more).
What is Time complexity?
Time complexity is defined as the amount of time taken by an algorithm to run, as a function of
the length of the input. It measures the time taken to execute each statement of code in an
algorithm. It is not going to examine the total execution time of an algorithm. Rather, it is going
to give information about the variation (increase or decrease) in execution time when the number
of operations (increase or decrease) in an algorithm indicating that the amount of time taken is a
function of the length of input only.
Space and Time define any physical object in the Universe. Similarly, Space and Time
complexity can define the effectiveness of an algorithm. While we know there is more than one
way to solve the problem in programming, knowing how the algorithm works efficiently can add
value to the way we do programming. To find the effectiveness of the program/algorithm,
knowing how to evaluate them using Space and Time complexity can make the program behave
in required optimal conditions, and by doing so, it makes us efficient programmers.
An Algorithm, in computer programming, is a finite sequence of well-defined instructions,
typically executed in a computer, to solve a class of problems or to perform a common task.
Based on the definition, there needs to be a sequence of defined instructions that have to be given
to the computer to execute an algorithm/ perform a specific task. In this context, variation can
occur the way how the instructions are defined. There can be any number of ways, a specific set
of instructions can be defined to perform the same task. Also, with options available to choose
any one of the available programming languages, the instructions can take any form of syntax
along with the performance boundaries of the chosen programming language. We also indicated
the algorithm to be performed in a computer, which leads to the next variation, in terms of the
operating system, processor, hardware, etc. that are used, which can also influence the way an
algorithm can be performed.
Now that we know different factors can influence the outcome of an algorithm being executed, it
is wise to understand how efficiently such programs are used to perform a task. To gauge this,
we require to evaluate both the Space and Time complexity of an algorithm.
By definition, the Space complexity of an algorithm quantifies the amount of space or memory
taken by an algorithm to run as a function of the length of the input. While Time complexity of
an algorithm quantifies the amount of time taken by an algorithm to run as a function of the
length of the input. Now that we know why Time complexity is so significant, it is time to
understand what is time complexity and how to evaluate it.
Time complexity measures the time taken to execute each statement of code in an algorithm. If a
statement is set to execute repeatedly then the number of times that statement gets executed is
equal to N multiplied by the time required to run that function each time.
The first algorithm is defined to print the statement only once. The time taken to execute is
shown as 0 nanoseconds. While the second algorithm is defined to print the same statement but
this time it is set to run the same statement in FOR loop 10 times. In the second algorithm, the
time taken to execute both the line of code – FOR loop and print statement, is 2 milliseconds.
And, the time taken increases, as the N value increases, since the statement is going to get
executed N times.
By now, you could have concluded that when an algorithm uses statements that get executed
only once, will always require the same amount of time, and when the statement is in loop
condition, the time required increases depending on the number of times the loop is set to run.
And, when an algorithm has a combination of both single executed statements and LOOP
statements or with nested LOOP statements, the time increases proportionately, based on the
number of times each statement gets executed.
This leads us to ask the next question, about how to determine the relationship between the input
and time, given a statement in an algorithm. To define this, we are going to see how each
statement gets an order of notation to describe time complexity, which is called Big O Notation.

Different Types of Time Complexity Notation

As we have seen, Time complexity is given by time as a function of the length of the input. And,
there exists a relation between the input data size (n) and the number of operations performed
(N) with respect to time. This relation is denoted as the Order of growth in Time complexity and
given notation O[n] where O is the order of growth and n is the length of the input. It is also
called as ‘Big O Notation’
Big O Notation expresses the run time of an algorithm in terms of how quickly it grows relative
to the input ‘n’ by defining the N number of operations that are done on it. Thus, the time
complexity of an algorithm is denoted by the combination of all O[n] assigned for each line of
function.
There are different types of time complexities used, let’s see one by one:
1. Constant time – O (1)
2. Linear time – O (n)
3. Logarithmic time – O (log n)
4. Quadratic time – O (n2)
5. Cubic time – O (n3)
and many more complex notations like Exponential time, Quasilinear time, factorial time, etc.
are used based on the type of functions defined
Constant time – O (1)
An algorithm is said to have constant time with order O (1) when it is not dependent on the input
size n. Irrespective of the input size n, the runtime will always be the same. For example, let’s
take a look at the function get_first which returns the first element of a list:
def get_first(data):
return data[0]
if __name__ == '__main__':
data = [1, 2, 9, 8, 3, 4, 7, 6, 5]
print(get_first(data))
Irrespective of the input data size, it will always have the same running time since it only gets the
first value from the list. An algorithm with constant time complexity is excellent since we don’t
need to worry about the input size.
O(1) time complexity, also known as constant time complexity, means that the running time of
an algorithm does not depend on the input size. In other words, no matter how large the input is,
the algorithm will always take the same amount of time to complete. This makes O(1) algorithms
very efficient, especially when working with large amounts of data. Another python example
def multiply_by_two(n):
return n * 2
print(multiply_by_two(10))
This Python code defines a function that multiplies a given number by two. The time taken to
execute this function is independent of the size of the input, which in this case is just a single
number. Hence, this code has O(1) time complexity.
In general, to determine the time complexity of an algorithm, we need to analyze how the
running time of the algorithm changes as the input size increases. If the running time remains
constant, the algorithm has O(1) time complexity
Linear time – O(n)
An algorithm is said to have a linear time complexity when the running time increases linearly
with the length of the input. When the function involves checking all the values in input data,
with this order O(n).
An algorithm is said to have a linear time complexity when the running time increases at most
linearly with the size of the input data, that is, when the function involves checking all the values
in input data, with this order O(n). This is the best possible time complexity when the algorithm
must examine all values in the input data. For example:
for value in data:
print(value)
Let’s take a look at the example of a linear search, where we need to find the position of an
element in an unsorted list; we need to look at all values in the list to find the value we are
looking for:
def linear_search(data, value):
for index in range(len(data)):
if value == data[index]:
return index
raise ValueError('Value not found in the list')
if __name__ == '__main__':
data = [1, 2, 9, 8, 3, 4, 7, 6, 5]
print(linear_search(data, 7))

Logarithmic time – O (log n)

An algorithm is said to have a logarithmic time complexity when it reduces the size of the input
data in each step. This indicates that the number of operations is not the same as the input size.
The number of operations gets reduced as the input size increases. Algorithms are found in
binary trees or binary search functions. This involves the search of a given value in an array by
splitting the array into two and starting searching in one split. This ensures the operation is not
done on every element of the data
An algorithm is said to have a logarithmic time complexity when it reduces the size of the input
data in each step (it don’t need to look at all values of the input data), for example:
for index in range(0, len(data), 3):
print(data[index])
Algorithms with logarithmic time complexity are commonly found in operations on binary trees
or when using binary search. Let’s take a look at the example of a binary search, where we need
to find the position of an element in a sorted list:
def binary_search(data, value):
n = len(data)
left = 0
right = n - 1
while left <= right:
middle = (left + right) // 2
 if value < data[middle]:
right = middle - 1
elif value > data[middle]:
left = middle + 1
else:
return middle
raise ValueError('Value is not in the list')

if __name__ == '__main__':
data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(data, 8))

Steps of the binary search:

Calculate the middle of the list.
If the searched value is lower than the value in the middle of the list, set a new right bounder.
If the searched value is higher than the value in the middle of the list, set a new left bounder.
If the search value is equal to the value in the middle of the list, return the middle (the index).
Repeat the steps above until the value is found or the left bounder is equal or higher the right
bounder.
It is important to understand that an algorithm that must access all elements of its input data
cannot take logarithmic time, as the time taken for reading input of size n is of the order of n.

Quadratic Time — O(n²)

An algorithm is said to have a non-linear time complexity where the running time increases non-
linearly (n2) with the length of the input. Generally, nested loops come under this order where
one loop takes O(n) and if the function involves a loop within a loop, then it goes for O(n)*O(n)
= O(n2) order.
Similarly, if there are ‘m’ loops defined in the function, then the order is given by O (n m), which
are called polynomial time complexity functions.
Thus, the above illustration gives a fair idea of how each function gets the order notation based
on the relation between run time against the number of input data sizes and the number of
operations performed on them
An algorithm is said to have a quadratic time complexity when it needs to perform a linear time
operation for each value in the input data, for example:
for x in data:
for y in data:
print(x, y)
Bubble sort is a great example of quadratic time complexity since for each value it needs to
compare to all other values in the list, let’s see an example:
def bubble_sort(data):
swapped = True
while swapped:
swapped = False
for i in range(len(data)-1):
if data[i] > data[i+1]:
data[i], data[i+1] = data[i+1], data[i]
swapped = True
if __name__ == '__main__':
data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
bubble_sort(data)
print(data)
Exponential Time — O(2n)
An algorithm is said to have an exponential time complexity when the growth doubles with each
addition to the input data set. This kind of time complexity is usually seen in brute-force
algorithms.
Another example of an exponential time algorithm is the recursive (a function that calls itself in
specific conditions) calculation of Fibonacci numbers:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
As you may have noticed, the time complexity of recursive functions is a little harder to define
since it depends on how many times the function is called and the time complexity of a single
function call. It makes more sense when the recursion tree is looked at. The following recursion
tree was generated by the Fibonacci algorithm using n = 4:

Note that it will call itself until it reaches the leaves. When reaching the leaves it returns the
value itself.
Now, look how the recursion tree grows just increasing the n to 6:
Now, let us start exploring the different types of Time Complexities
What are the Different Types of Time Complexities?
There are different types of time complexities used in Algorithms as shown below:

Constant Time Complexity

Linear Time Complexity
Logarithmic Time Complexity
Quadratic Time Complexity
Cubic Time Complexity
Exponential Time Complexity
Quasilinear Time Complexity
Factorial Time Complexity
and many more complex notations are used on the basis of the type of functions defined.
The time complexities in detail.
Constant Time Complexity - O (1)
The time complexity of an algorithm is said to be constant when the algorithm is not dependent
on the input size n. The runtime of such an algorithm remains the same irrespective of the input
size n. This time complexity is denoted as O (1).
Let us consider the following snippet of code illustrating the same.

Example
In the above snippet of code, we have defined a function as getFirstElement() that accepts a list
as an argument. In this function, we have returned the first data element of the list. For the main
function, we have initialized two arrays with 10 elements and 7 elements, respectively, and
called the getFirstElement() function by passing the initialized arrays to it and printing the first
element of both arrays.
The above code shows that irrespective of the length of the array (n), the runtime to get the first
element in an array of any length is the same. If the run time is considered as 1 unit of time, then
it takes only 1 unit to execute the arrays, irrespective of the length. Thus, the function comes
under constant time with order O (1).
Linear Time Complexity - O (n)
The time complexity of an algorithm is said to be linear when the run time of the algorithm
increases linearly with the length of the input. This statement implies that whenever a function
has an iteration that iterates over an input size of n, the algorithm will have a time complexity of
order O (n).

Let us consider the following snippet of code illustrating the same.

Example:
In the above snippet of code, we have defined a function as printElements() that accepts a list as
an argument. In this function, we have used the FOR loop to iterate through the list and print the
data element of the list. For the main function, we have initialized an array with 10 elements. We
then printed a statement for the users and called the printElements() function by passing the
initialized array to it to print the elements of an array.
The above code shows that the run time will increase linearly on the basis of the length of the
array (n). If the run time is considered 1 unit of time, then it will take only n time s 1 unit to
execute the array. Thus, the function runs linearly with the input size, which comes with order O
(n).
Logarithmic Time Complexity - O (log n)
The time complexity of an algorithm is said to be logarithmic if that algorithm reduces the size
of the input data in each step. This statement implies that the number of operations performed in
the function is different from the input size. However, the number of operations reduces as the
size of the input data increases. This time complexity is denoted as O (log n).
Algorithms having such time complexity are generally found in operations on binary trees and
binary search functions. Such an algorithm involves the search of a given value in an array by
splitting the array into two and starting to search in one split. This method ensures that the
operation is not done on every data element of the list.