Algorithm Analysis and Time Complexity
1
Algorithms Analysis
If you run the same program on a computer, cellphone, or even a smartwatch, will it take
same time or different time?
Wouldn’t it be great if we can compare algorithms regardless of the hardware where we run
them?
That’s what time complexity is for!
But, why stop with the running time?
We could also compare the memory "used" by different algorithms, and we call that space
complexity.
2
What is an Algorithm?
An Algorithm is a set of step by step instructions to be followed to solve a particular
problem.
Characteristics of an Algorithm
Input Algorithm Output
Write an algorithm to find the maximum value from N numbers
3
Algorithm to find the maximum value from N numbers
Step 1: Read N.
Step 2 : Let Counter = 1.
Step 3: Read a Number.
Step 4 : Maximum = Number.
Step 5: Read next Number.
Step 6 : Counter = Counter + 1.
Step 7 : If ( Number > Maximum ) then Maximum = Number.
Step 8 : If ( Counter < = N ) then go to step 5.
Step 9: Print Maximum.
Step 10: End.
4
Comparing Algorithms
Not all algorithms are created equal.
There are “good” and “bad” algorithms.
The good ones are fast; the bad ones are slow.
Slow algorithms cost more money to run.
Inefficient algorithms could make some calculations impossible in our lifespan!
Let’s say you want to compute the shortest path from Bombay to Surathkal.
Slow algorithms can take hours or crash before finishing.
On the other hand, a "good" algorithm might compute in a few seconds.
Usually, algorithms time grows as the size of the input increases.
For instance, calculating the shortest distance from your hostel room to NITK
beach will take less time than other destination thousands of miles away.
5
Relationship between algorithm input size and time taken to
complete
Input size → 10 100 10k 100k 1M
Finding if a
< 1 sec. < 1 sec. < 1 sec. < 1 sec. < 1 sec.
number is odd
Sorting array with
< 1 sec. < 1 sec. < 1 sec. few sec. 20 sec.
merge sort
Sorting array with
< 1 sec. < 1 sec. 2 minutes 3 hours 12 days
Selection Sort
Finding all 40,170 trillion
< 1 sec. > centillion years ∞ ∞
subsets years
Finding string > vigintillion
4 sec. > centillion years ∞ ∞
permutations years
6
Relationship between algorithm input size and time taken to
complete
As you can see in the table, most algorithms on the table are affected by the
input size.
But not all and not at the same rate.
Finding out if a number is odd will take the same if it is 1 or 1 million.
We say then that the growth rate is constant.
Others grow very fast.
Finding all the permutations on a string of length 10 takes a few seconds,
while if the string has a size of 100, it won’t even finish!
7
Calculating Time Complexity
In computer science, time complexity describes the number of operations a
program will execute given the size of the input n.
1. int findMaximum ( int array[ ], int n)
2. { int maximum = array[0]; 1 Operation
3. for ( int i=1; i<n; i++) 1 Loop n-1 times
4. if ( maximum < array[i]) 1 Operation
5. maximum = array[i]; 1 Operation
6. return( maximum); 1 Operation
7. } 2(n-1) + 2
Assuming that each line of code is an operation, we get 2(n-1) +
2
8
Calculating Time Complexity
For input size n=5, 2(n-1) + 2 = 10 operations.
For input size n=8, 2(n-1) + 2 = 16 operations.
This is not for every case. Line 5 executed only if line 4 condition is TRUE.
So, we need the big picture and get rid of smaller terms to compare algorithms
easier.
Asymptotic analysis describes the behavior of functions as their inputs approach to
infinity.
9
Running Time
best case
Most algorithms transform input average case
objects into output objects. worst case
120
The running time of an algorithm
typically grows with the input size. 100
Running Time
Average-case running time is often 80
difficult to determine. 60
We focus on the worst case running 40
time.
20
Easier to analyze
0
Crucial to applications such as games, 1000 2000 3000 4000
finance and robotics Input Size
10
All algorithms have three scenarios:
Best-case scenario: the most favorable input arrangement where the program will
take the least amount of operations to complete.
E.g., a sorted array is beneficial for some sorting algorithms.
Average-case scenario: this is the most common case.
E.g., array items in random order for a sorting algorithm.
Worst-case scenario: the inputs are arranged in such a way that causes the program
to take the longest to complete.
E.g., array items in reversed order for some sorting algorithm will take the longest
to run.
11
Average Case vs. Worst Case
The average case running time is
harder to analyze because you
need to know the probability
distribution of the input.
In certain apps (air traffic
control, weapon systems,etc.),
knowing the worst case time is
important.
12
Experimental Approach
9000
Write a program implementing the 8000
algorithm 7000
6000
Run the program with inputs of
Time (ms)
5000
varying size and composition
4000
Use a wall clock to get an accurate 3000
measure of the actual running time 2000
1000
Plot the results
0
0 50 100
Input Size
13
Limitations of Experiments
It is necessary to implement the algorithm, which may be
difficult and often time-consuming
Results may not be indicative of the running time on
other inputs not included in the experiment.
In order to compare two algorithms, the same hardware
and software environments must be used
Restrictions
14
Theoretical Analysis
Uses a high-level description of the algorithm instead
of an implementation
Characterizes running time as a function of the input
size, n.
Takes into account all possible inputs
Allows us to evaluate the speed of an algorithm
independent of the hardware/software environment
15
Simplifying Complexity with Asymptotic Analysis
What is Big O Notation?
Big O, where O refers to the order of a function in the worst-case scenario.
Big O = Big Order (rate of growth) of a function.
If you have a program that has a runtime of: 7n3 + 3n2 + 5
You can express it in Big O notation as O(n3). The other terms (3n2 + 5) will become
less significant as the input grows bigger.
Big O notation only cares about the “biggest” terms in the time/space complexity.
16
17
18
19
How long an algorithm takes to run based on their
time complexity and input size
Input Size O(1) O(n) O(n log n) O(n2) O(2n) O(n!)
1 < 1 sec. < 1 sec. < 1 sec. < 1 sec. < 1 sec. < 1 sec.
10 < 1 sec. < 1 sec. < 1 sec. < 1 sec. < 1 sec. 4 seconds
10k < 1 sec. < 1 sec. < 1 sec. 2 minutes ∞ ∞
100k < 1 sec. < 1 sec. 1 second 3 hours ∞ ∞
1M < 1 sec. 1 second 20 seconds 12 days ∞ ∞
This is just an illustration since, in different hardware, the times will be distinct. These times are under the assumption
of running on 1 GHz CPU, and it can execute on average one instruction in 1 nanosecond (usually takes more time).
Note
Also, keep in mind that each line might be translated into dozens of CPU instructions depending on the programming
language.
20
Space Complexity
Space complexity is similar to time complexity.
Instead of the count of operations executed, it will account for the amount of
memory used additionally to the input.
For calculating the space complexity, we keep track of the “variables” and memory
used.
In the findMaximum example, we create a variable called maximum, which only
holds one value at a time. So, the space complexity is 1.
On other algorithms, If we have to use an auxiliary array that holds the same
number of elements as the input, then the space complexity would be n.
21
Pseudocode
High-level description of Example: find the max
an algorithm element of an array
More structured than Algorithm arrayMax(A, n)
english prose Input array A of n integers
Less detailed than a Output maximum element of A
program currentMax A[0]
Preferred notation for for i 1 to n 1 do
describing algorithms if A[i] currentMax then
currentMax A[i]
Hides program design return currentMax
issues
22
Pseudocode Details
Control flow
Method call
if … then … [else …] var.method (arg [, arg…])
Return value
while … do …
return expression
repeat … until … Expressions
for … do … Assignment (like in C, C++)
Equality testing
Indentation replaces braces (like in C, C++)
n2 Superscripts and other
Method declaration mathematical formatting
allowed
Algorithm method (arg [, arg…])
Input …
Output …
23
