Time Complexity

Algorithm Definition
A finite set of statements that guarantees an optimal solution in finite
interval of time

8/21/2024 BY MS ANOSHA KHAN

Good Algorithms?
Run in less time

Consume less memory

But computational resources (time complexity) is usually more

important

8/21/2024 BY MS ANOSHA KHAN

Measuring Efficiency
The efficiency of an algorithm is a measure of the amount of resources
consumed in solving a problem of size n.
◦ The resource we are most interested in is time
◦ We can use the same techniques to analyze the consumption of other resources, such
as memory space.

It would seem that the most obvious way to measure the efficiency of an
algorithm is to run it and measure how much processor time is needed

8/21/2024 BY MS ANOSHA KHAN

Factors
Hardware
Operating System
Compiler
Size of input
Nature of Input
Algorithm
Which should be improved?

8/21/2024 BY MS ANOSHA KHAN

RUNNING TIME OF AN ALGORITHM
Depends upon
◦ Input Size
◦ Nature of Input

Generally time grows with size of input, so running time of an algorithm is

usually measured as function of input size.
Running time is measured in terms of number of steps/primitive operations
performed
Independent from machine, OS

8/21/2024 BY MS ANOSHA KHAN

 Finding running time of an Algorithm / Analyzing an
Algorithm
Running time is measured by number of steps/primitive operations performed

Steps means elementary operation like

◦ ,+, *,<, =, A[i] etc

We will measure number of steps taken in term of size of input

8/21/2024 BY MS ANOSHA KHAN

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.
8/21/2024 BY MS ANOSHA KHAN
Execution Time Cases
Worst Case − This is the scenario where a particular data structure operation
takes maximum time it can take. If an operation's worst case time is ƒ(n) then
this operation will not take more than ƒ(n) time where ƒ(n) represents
function of n.
Average Case − This is the scenario depicting the average execution time of
an operation of a data structure. If an operation takes ƒ(n) time in execution,
then m operations will take mƒ(n) time.
Best Case − This is the scenario depicting the least possible execution time of
an operation of a data structure. If an operation takes ƒ(n) time in execution,
then the actual operation may take time as the random number which would
be maximum as ƒ(n).

8/21/2024 BY MS ANOSHA KHAN

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.
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 10
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.
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 11
Asymptotic Analysis
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.
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 12
Asymptotic Notations
Following are the commonly used asymptotic notations to calculate
the running time complexity of an algorithm.
Ο Notation
Ω Notation
θ Notation

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 13

 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

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 14

 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

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 15

 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

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 16

 Types of Notations for Time
Complexity
Now we will discuss and understand the various notations used for Time
Complexity.
[Link] Oh denotes "fewer than or the same as" <expression>
iterations.
[Link] Omega denotes "more than or the same as" <expression>
iterations.
[Link] Theta denotes "the same as" <expression> iterations.
[Link] Oh denotes "fewer than" <expression> iterations.
[Link] Omega denotes "more than" <expression> iterations.
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 17
Common Asymptotic Notations

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 18

 Calculating Time Complexity
Now lets tap onto the next big topic related to Time complexity,
which is How to Calculate Time Complexity. It becomes very
confusing some times, but we will try to explain it in the simplest
way.
Now the most common metric for calculating time complexity is
Big O notation. This removes all constant factors so that the
running time can be estimated in relation to N, as N approaches
infinity. In general you can think of it like this :

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 19

Guideline 1
The running time of a comments, declarative and function
statements count to zero

template <class Type>

Declarative Statements
class List ;
int age;
comments //a variable to store age
Function statements void Print();

Total time = zero

8/21/2024 BY MS ANOSHA KHAN

Guideline 2
Expressions, memory management & assignment statements for
primitive data types have constant running time i.e. one.

int a = 4+5;
Expressions and
assignment statements
char b =‘a’;

Memory Management
int * a = new int;
statements delete a;

Total time = constant

8/21/2024 BY MS ANOSHA KHAN

Guideline 3
Memory management & assignment statements for objects have
constant running time i.e. size of object.

Student a,b;
Memory Management
statement of object Student * a = new Student;
delete a;
Assignment statement
of object a = b;

Total time = constant

8/21/2024 BY MS ANOSHA KHAN

Guideline 4
Function invocations count as 1 step unless the invocation involves
pass by value parameter whose size depends on the instance
characteristics i.e. sizes of the value parameters

Total time = constant

8/21/2024 BY MS ANOSHA KHAN

statement;
Above we have a single statement. Its Time Complexity will be Constant. The
running time of the statement will not change in relation to N.
for(i=0; i < N; i++)
{
statement;
}
The time complexity for the above algorithm will be Linear. The
running time of the loop is directly proportional to N. When N
doubles, so does the running time.

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 24

Guideline 5: Loops
The running time of a loop is, at most, the running time of the
statements inside the loop (including tests) multiplied by the number
of iterations.

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

executed {
n times constant time
m = m + 2;
}
Total time = (constant) c * n = cn

8/21/2024 BY MS ANOSHA KHAN

8/21/2024 BY MS ANOSHA KHAN
Problems with T(n)
•T(n) is difficult to calculate
•T(n) is also not very meaningful as step size is not exactly defined
•T(n) is usually very complicated so we need an approximation of
T(n)….close to T(n).
•This measure of efficiency or approximation of T(n) is called
ASYMPTOTIC COMPLEXITY or ASYMPTOTIC ALGORITHM
ANALYSIS

Asymptotic complexity studies the efficiency of an algorithm as

the input size becomes large

27
Example
If T(n) = 7n+100
What is T(n) for different values of n???

n T(n) Comment
1 107 Contributing factor is 100
5 135 Contributing factor is 7n and 100
10 170 Contributing factor is 7n and 100
100 800 Contribution of 100 is small
1000 7100 Contributing factor is 7n
10000 70100 Contributing factor is 7n
106 7000100 What is the contributing factor????

When approximating T(n) we can IGNORE the 100 term for very
large value of n and say that T(n) can be approximated by 7(n)
 Example 2

T(n) = n2 + 100n + log10n +1000

n T(n) n2 100n log10n 1000

Val % Val % Val % Val %

1 1101 1 0.1% 100 9.1% 0 0% 1000 90.8%
10 2101 100 5.8% 1000 47.6% 1 0.05% 1000 47.6%
100 21002 10000 47.6% 10000 47.6% 2 0.99% 1000 4.76%
105 10,010,001,005 1010 99.9% 107 .099% 5 0.0% 1000 0.00%

When approximating T(n) we can IGNORE the last 3 terms and

say say that T(n) can be approximated by n2
Problems with solutions
Problem 1
sum = 0;
for( i = 0; i < n; i++)
sum++;
The running time for the operation sum++ is a constant. The loop
runs n times, hence the complexity of the loop would be O(n)

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 30

for(i=0; i < N; i++)
{
for(j=0; j < N;j++)
{
statement;
}
}
This time, the time complexity for the above code will be
Quadratic. The running time of the two loops is proportional to
the square of N. When N doubles, the running time increases by N
* N.
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 31
Guideline 6: Nested loops
Analyse inside out. Total running time is the product of the
sizes of all the loops.

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

outer loop for (j=1; j<=n; j++) { inner loop
executed executed
n times
k = k+1; n times
}
} constant time

Total time = c * n * n * = cn2

8/21/2024 BY MS ANOSHA KHAN

Problem 2
sum = 0;
for( i = 0; i < n; i++)
for( j = 0; j < n; j++)
sum++;
The running time for the operation sum++ is a constant.
The outer loop runs n times, The nested loop also runs n times,
hence the complexity would be
O(n2)

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 33

Guideline 7: Consecutive statements
Add the time complexities of each statement.

constant time c0 x = x +1;

for (i=1; i<=n; i++) {
m = m + 2;
executed
constant time c1
} n times
for (i=1; i<=n; i++) {
outer loop for (j=1; j<=n; j++) { inner loop
executed k = k+1; executed
n times } n times
constant time c2
}

Total time = c0 + c1n + c2n2

8/21/2024 BY MS ANOSHA KHAN

Guideline 8: If-then-else statements
if( exp)
statements1;
else
statements2;
Cost is the number of steps corresponding to
exp, statements1 and statements2.

If exp: if (depth( ) != [Link]( ) ) {

Constant c0 return false; Statements1:
} Constant c1
else {
for (int n = 0; n < depth( ); n++) {
else part:
another if : if (!list[n].equals([Link][n]))
return false;
(constant c2 +
constant +
} Constant c3) * n
constant
(no else part) }

Total time = c0 + c1 + (c2 + c3) * n

8/21/2024 BY MS ANOSHA KHAN

while(low <= high)
{
mid = (low + high) / 2;
if (target < list[mid])
high = mid - 1;
else if (target > list[mid])
low = mid + 1;
else break;
}
This is an algorithm to break a set of numbers into halves, to search a particular
field. Now, this algorithm will have a Logarithmic Time Complexity. The running
time of the algorithm is proportional to the number of times N can be divided by 2.
This is because the algorithm divides the working area in half with each iteration.
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 36
Problem 3
sum = 0;
for( i = 0; i < n; i++)
for( j = 0; j < n * n; j++)
sum++;
The running time for the operation sum++ is a constant.
The outer loop runs n times, The nested loop runs n * n times,
hence the complexity would be
O(n3)

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 37

Problem 4
sum = 0;
for( i = 0; i < n; i++)
for( j = 0; j < i; j++)
sum++;
The running time for the operation sum++ is a constant.
The outer loop runs n times. For the first execution of the outer loop the inner
loop runs only once. For the second execution of the outer loop the inner loop
run twice, for the third execution - three times, etc. Thus the inner loop will be
executed 1 + 2 + ... + (n-1) + n times.
1 + 2 + ... + (n-1) + n = n(n+1) / 2, which gives (n+1) / 2 on average.
Thus the total running time would be O(n*(n+1)/2) = O(n*n) = O(n2)
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 38
Problem 5
sum = 0;
for( i = 0; i < n; i++)
for( j = 0; j < i*i; j++)
for( k = 0; k < j; k++)
sum++;
The running time for the operation sum++ is a constant.
The most inner loop runs at most n*n times, the middle loop also
runs at most n*n times, and the outer loop runs n times, thus the
overall complexity would be O(n5)

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 39

Problem 6
sum = 0;
for( i = 0; i < n; i++)
sum++;
val = 1;
for( j = 0; j < n*n; j++)
val = val * j;
First, we assume that the running time to compute an arithmetic
expression without function calls is negligible. Then, we have two
consecutive loops with running times O(n) and O(n2). We take the
maximum complexity, hence the overall running time would be
O(n2)
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 40
Problem 7
sum = 0;
for( i = 0; i < n; i++)
sum++;
for( j = 0; j < n*n; j++)
compute_val(sum,j);
The complexity of the function compute_val(x,y) is given to be
O(nlogn)
The second loop runs n*n times, so its complexity would be
O(n2 *nlogn) = O(n3logn).
The first loop has less running time - O(n), we take the maximum and
conclude that the overall running time would be O(n3logn)
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 41
Problem 8
for( i = n; i >1; i = i/2 )
{…… }
for( i = 1; i <n; i = i*2 )
{……. }

Running time: O( [running time of the body] * Log(N))

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 42

Important points
Is it true that NlogN = o(N2) ?
Compare NlogN and N:
NlogN = O(N) or N = O(NlogN) ?
Is it true that NlogN = o(N) ?
N2 + NlogN = ?
N + NlogN = ?
N2 + logN = ?

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 43

Growth rates
Which growth rate is better???

Graph from Adam Drozdek’s book

Comparison of Growth Rates
N log2N N log2N N2 N3 2N

1 0 0 1 1 2

2 1 2 4 8 4

8 3 24 64 512 256

64 6 384 4096 262,144 18446744073709551616

128 7 896 16,384 2,097,152 Approx 6 billion years,

600,000 times more than
age of univ.

(If one operation takes 10-11 seconds)

Big O??
Running Time: O(1)+O(n)+O(n)= O(n)
void print(int * array, int size){
cout<<"Array: ";
for(int i = 0; i < size; i++)
O(n) cout <<array[i]<<" ";
cout<<endl;
}
int smallest(int array[], int size, int start){
if(start == size-1)
O(1) return start;
else
{
int small = start;
O(n for(int i = start+1; i <size; i++){
) if(array[small]>array[i])
O(n) small= i;
}
return small;
}
}
void main(){
O(1) const int n= 5;
int array[n]={3,5,9,6,1};
O(n cout<<"Smallest: "<<array[smallest(array,n,0)]<<endl;
print(array,n);
) }
O(n
)
Big-O?
void sortArray(int * a, int size){
for(int i = 0;i<size;i++){
O(n2) O(n int small = smallest(a,size,i);
O(n) ) int temp = a[i];
O(1) a[i] = a[small];
a[small] = temp;
}
}

void main(){
const int n= 5;
int array[n]={3,5,9,6,1};
sortArray(array,n);
print(array,n);
}

Running Time: O(1)+O(n2)+O(n)= O(n2)

Big-O?

void main(){
const int n= 5;
int array[n]={3,5,9,6,1};
for(int i =0; i <n; i++)
O(n3 O(n2)sortArray(array,n);
) print(array,n);
}

Running Time: O(1)+ O(n3) = O(n3)

Big-O?
bool BinarySearch(int * a,int size, int search){
int high = size-1;
int low = 0;
int mid ;
while (low<=high){
mid = (high+low)/2;
if(a[mid]==search)
return true;
else if(search < a[mid]){
high = mid-1;
}
else
low = mid+1;
}
return false;
}
 Iteration 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Low Mid High

Iteration 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Low Mid High

Iteration 3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Low High
Mid
Iteration 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Low High n =16 = 24

Mid Iterations = 4
Log224= 4 O(log2n)
Exercise
Arrange these functions in order of increasing
rate of growth.
Identify any functions with the same rate of
growth.
2 n+2 2 6 2 4 6 2
n , 2 , nlog n, n!, n + log n, n , n - n ,
n n 2n
4 , n, n , 2 .

8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 51

Solution
n
2
nlog n
2
n
n4
6 2 6 2
n + log n, n - n (same rate)
n+2
2
n 2n
4 , 2 (same rate)
n!
nn
8/21/2024 DATA STRUCTURES , PROF. ANOSHA KHAN 52
8/21/2024 BY MS ANOSHA KHAN
8/21/2024 BY MS ANOSHA KHAN
8/21/2024 BY MS ANOSHA KHAN
8/21/2024 BY MS ANOSHA KHAN