Complexity of Algorithm
(Algorithm Complexity)
By Arshad Ibrahim.
What is Complexity of Algorithm?
Complexity of algorithm is the process of measuring how efficiently
your code runs. It tells you how much time and space your program
needs as the input size grows. Understanding complexity helps you
write faster, smarter code.
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
decides the efficiency of X.
Low Time Time and Space
Complexity
High Time, High Time Complexity: Time complexity of
High Time, Low Space
Space
an algorithm represents the amount of
Low Space High Space
time required by the algorithm to run
to completion.
Low Time, High Space Low Time, Low Space Space Complexity: Space complexity
of an algorithm represents the amount
High Time
of memory space required by the
algorithm in its life cycle.
We take three cases for complexity of algorithms.
Best Case ( ) Ω Average Case ( ) Θ Worst Case (O)
It is called Ω (omega) notation. It It is called Θ (theta) notation. It It is called Big O notation. It
indicates the minimum time an means algorithm's performance is guarantees that an algorithm will
algorithm needs to execute. restricted between a specific never take more than a specific
upper and lower limit. amount of time.
Example of sorting
N elements:
If the input values are in reverse order,
an algorithm will require maximum
time to sort them. This will become a
worst case scenario.
Worst Case: Worst case time
complexity always guarantees that
the algorithm will always execute
within this time for different input
values.
Calculating Time Complexity: (Slide 1)
The most common notation we use to calculate time complexity is Big O notation. It will remove all the constant values
that takes the same amount of time in operations, regardless of input size. So the running time can be estimated as N. N
represents Infinity. In general, we consider it as; statement;
statement;
In the above code, we have a single statement. Its complexity will be constant. The running time of the statement will not
change in relation to N.
Calculating Time Complexity: (Slide 2)
for(int i = 0; i < N; i++)
{
statement;
}
The time complexity for the above statement will be linear. The running time of the loop is directly propositional to N.
Calculating Time Complexity: (Slide 3)
for(i = 0; i < N; i++)
{
for(j = 0; j < N; j++)
{
statement;
}
}
The time complexity for the above code will be Quadratic. The running time of the two loops is propositional to the
square of N. When N doubles, the running time increases by N * N.
Calculating Time Complexity: (Slide 4)
while(low <= high)
{
mid = (low + high) / 2;
if(x < list[mid])
high = mid - 1;
else if(x > list[mid])
low = mid + 1;
else break;
}
This is an algorithm to break a set of networks into halves, to search a particular field. Now, this algorithm will have a
Logarithmic Time Complexity. The running time of the algorithm is propositional to the number of times N can be divided
by 2. This is because the algorithm divides the working area in half in each iteration.
Space Complexity
Space complexity is the sum of following two memory:
Fixed size memory: It contains the space required for
simple variables, constants, instructions and fixed
size structured variable such as array.
Variable size memory: It contains the space required
for structured variable to which memory is allocated
at run time. It also contains space required while
function calling itself.
Thank You