Understanding Time

Complexity
Understanding
Time Complexity
Complexity of Algorithms
• The complexity of an algorithm is the function which gives the running
time and/or space in terms of the input size.
• In order to compare algorithms, we must have some criteria to measure
the efficiency of a algorithm.
• Suppose M is an algorithm, and suppose n is the size of the input data.
• The TIME and SPACE used by the algorithm M are the two main
measures for the efficiency of M.
• The TIME is measured by counting the number of key operation-in
sorting and searching algorithms. (the # of comparison)
• The SPACE is measured by counting the maximum of memory needed
by the algorithm
©️ Dr. Md. Golam Rashed, Assoc. Professor, Dept. of ICE, RU ICE 2231/ Introduction
“IN Computer
Science, time
complexity
describes the
amount of time
that takes to run
an algorithm or
Code.”
 How to
calculate
Time
Complexity ?

“Time complexity is
calculated by counting
the Number of
Operation , which
takes a fixed amount
of time to perform.”
 Big O Notation

“Big O notation is
a mathematical
notation that
describes the
limiting behavior
of a function
when the
argument tends
towards a
particular value or
infinity.”
•O(1) Constant Time complexity
•O(N) Linear Time Complexity
Common Time Complexity
•O(N^2) Quadratic Time Complexity
•O(N log N) Logarithmic Time
Complexity
 Constant Time Complexity-O(1)

#include <iostream>
using namespace std;
➢Input ( in single operation)
➢Output (in single operation)
int main() {

int a,b;
cin >> a >> b;
//O(1+1)=O(1) constant operation.
int sum = a+b;
cout<< sum <<endl;
return 0;
}
Linear Time Complexity - O(N)

#include<bits/stdc++.h>
using namespace std;
int main()
o While doing operation with {
Single for or while loop. int t;
cin >> t;
int n;
cin >> n;
int arr[n];
for(int i=0;i<n;i++){
• Total Complexity( O(N) )
cin >> arr[i];
• In 1 Sec 1e7 Or maximum 1e8 } // O(N) *here N is Number of
Iteration can be done. element
sort(arr,arr+n);
for(int i=0;i<n;i++){
cout << i << " ";
} // O(N) *here N is Number of
element
cout << endl;
}
Quadratic Time Complexity – O(N^2)
#include<bits/stdc++.h>
• “If Two nested loop used and using namespace std;
iterate through all the int main()
{
elements. Then complexity is int n;
O(n^2).” cin >> n;
• Explanation : iteration for the int arr[n];
for(int i=0;i<n;i++) cin >> arr[i];
inner loop : (n-1)*(n- //Bubble sort
2)……*2*1. for( int i = 0; i < n; i++ )
{
• So the result is n*(n-1) which
for(int j = 0; j < (n-i-1); j++) {
is O(n^2). if(arr[j] > arr[j+1]){
swap( arr[j] , arr[j+1] );
}
} }
for(auto u : arr){
cout << u << " ";
}
cout << endl;
}
Logarithmic Time Complexity – O(log N) int main()
{ // Binary Search
Per Operation mid divides into int n , v[n]; cin >> n;
half Value. That means for(int i=0; i<n; i++){
cin >> v[i];
n/2 + n/4 + n/8 + n/16 + …….. }
= n (1/2 + 1/4 + 1/8 + …….. ) int lo=0,hi=n-1,mid,fnd;
cin >> fnd;
= log(n)) // log2(y) = x, 2^x while(hi>=lo){
= y; mid=(hi+lo)/2;
if(v[mid] == fnd) {
So, Time Complexity of cout << mid << endl;
Binary search is break;
O(log(n)) }
if(v[mid] <= fnd){
lo=mid+1; }
else
{
hi = mid-1;
} }}
Flowcharts

©️ Dr. Md. Golam Rashed, Assoc. Professor, Dept. of ICE, ICE 2231/ Introduction