Efficiency and
Computational Complexity
What is a “good” algorithm/
program?
• Solution is simple but powerful/general
• Easily understood by reader
• Easily modifiable and maintainable
• Correct for clearly defined situations
• Efficient in space and time
• Well documented
– usable by those who do NOT understand the detailed
working
• Portable across computers
• Can be used as a sub-program
Courtesy Prof P. R. Panda, CSE, IIT Delhi 2
Efficiency of Algorithms
• Algorithms/Programs evaluated in terms
of:
– execution time
– memory space
Courtesy Prof P. R. Panda, CSE, IIT Delhi 3
Identifying Redundant
Computation
x=0
for i in range(10):
• Redundant y=(a*a*a+c)*x*x + (b*b)*x +c
print(y)
computation x=x+0.01
can be moved
from loop
– loop-invariant x=0
t1 = (a*a*a + c)
computation t2 = b*b
for i in range(10):
y=t1*x*x + t2*x +c
print(y)
x=x+0.01
Courtesy Prof P. R. Panda, CSE, IIT Delhi 4
Computational Complexity
• Quantitative measure of algorithm’s performance
needed
– independent of programming language
– independent of machine
• Performance is characterised in terms of size of the
problem being solved
– if problem size is n (e.g., searching in array of n integers)
– how many operations are performed by algorithm?
• as a function of n
• indirectly measures execution time
– how much memory is required for storage
• as a function of n
Courtesy Prof P. R. Panda, CSE, IIT Delhi 5
Rate of growth of functions
y = 2x
y = ax2 + b
y = ax + b
y = log x
Courtesy Prof P. R. Panda, CSE, IIT Delhi 6
Asymptotic Analysis
• What happens for large n?
Courtesy Prof P. R. Panda, CSE, IIT Delhi 7
Order Notation
• Function g(n) is of order O(f(n)) if
– there exists c for which g(n) ≤ cf(n)
– for all n ≥ some n1
Courtesy Prof P. R. Panda, CSE, IIT Delhi 8
Rate of Growth of Functions
• Given f(n) and g(n), which grows faster?
– If Limn→∞f(n)/g(n) = 0, then g(n) is faster
– If Limn→∞f(n)/g(n) = ∞, then f(n) is faster
– If Limn→∞f(n)/g(n) = non-zero constant, then both
grow at the same rate
• Two polynomials of the same degree grow at
the same rate
• O(1) means constant time
– independent of n
Courtesy Prof P. R. Panda, CSE, IIT Delhi 9
Why use O( ) for measuring
Complexity?
• Hiding constants
– crude/approximate
– easier to compute
– holds across machines
• How does algorithm scale for increasing n?
• Which algorithm is better for large problem
size?
Courtesy Prof P. R. Panda, CSE, IIT Delhi 10
Computing the Complexity
• Estimate the number of
operations
– as a function of input size def largest(L):
lelement=L[0]
• One for initialisation for i in range(len(L)):
• Loop executes n times if (L[i]>lelement):
– Max. of one comparison and one lelement=L[i]
return lelement
assignment in each iteration
– Max. 2n operations for loop
• Total operations = 1 + 2n
• Complexity is O(n)
Courtesy Prof P. R. Panda, CSE, IIT Delhi 11
Complexity of Matrix Multiplication
• In k-loop
– 2 operations: one +, one *
ALGORITHM MatMult (int n)
– n iterations BEGIN
– 2n operations for i = 1 to n
• In j-loop for j = 1 to n
BEGIN
– 1 assignment
C[i][j] = 0
– 2n operations in k-loop for k = 1 to n
– n iterations C[i][j] = C[i][j] + A[i][k] * B[k][j]
– Total = n * (2n+1) operations END
END
• In i-loop
– n iterations
– Total = n * n * (2n+1) operations
• Complexity is O(n3)
Courtesy Prof P. R. Panda, CSE, IIT Delhi
Efficient Algorithms
• Problem:
– Given real number x and integer n
– Write an algorithm to calculate xn
Courtesy Prof P. R. Panda, CSE, IIT Delhi 13
First Algorithm
• Power
– power(x,n) = 1 for n = 0
– power(x, n) = x * power(x,n-1) for n>1
def power(x,n):
if (n==0):
return 1
else:
return x*power(x,n-1)
Courtesy Prof P. R. Panda, CSE, IIT Delhi 14
Recurrence Relation
• Power
– T(n) = 1, if n = 0
– T(n) = T(n-1) + 1, otherwise
Solving Recurrence Relations
• By Telescoping
– substitution
T(n) = T(n-1) + 1
= T(n-2) + 2
= T(n-3) + 3
...
= T(2) + n-2
= T(1) + n-1
= T(0) + n
=1+n
= O(n)
Fast Algorithm
• Fast Power
def fpower(x,n):
if (n==0):
return 1
else:
y = fpower(x,int(n/2))
if (n%2 == 0):
return y*y
else:
return x*y*y
Courtesy Prof P. R. Panda, CSE, IIT Delhi 17
Recurrence Relation
• Fast Power
– T(n) = 1, if n = 0
– T(n) = 1, if n = 1
– T(n) = T(n/2) + c, otherwise
Solving Recurrence Relations
• By Telescoping
– substitution
T(n) = T(n/2) + c
= T(n/22) + 2c
= T(n/23) + 3c
...
= T(n/2m-1) + (m-1)c
= T(n/2m) + mc
= O(m)
= O(log2n)
...where m = log2n
Binary Search
mid
L U
• “Divide and
Conquer” strategy # Algorithm Binary Search
– at every stage, we def binarysearch(ar, l, r, x):
reduce the size of
the problem to half while l<=r:
the earlier stage mid = l+(r-l)//2
• Strategy: Compare if ar[mid] == x:
return mid
with the middle
elif ar[mid] < x:
element of current l = mid + 1 Iterative
range, and else:
eliminate half of r = mid - 1
the range
return -1
Courtesy Prof P R Panda CSE, IIT Dellhi 20
Binary Search
mid
L U
Recursive # Algorithm Binary Search
def binarysearch (ar, l, r, x):
if r >= l:
mid = l + (r - l)//2
if ar[mid] == x:
return mid
elif ar[mid] > x:
return binarysearch(ar, l, mid-1, x)
else:
return binarysearch(ar, mid+1, r, x)
else:
return -1
Courtesy Prof P R Panda CSE, IIT Dellhi 21
Recurrence Relation
• Binary Search
– T(n) = 1, if n = 1
– T(n) = T(n/2) + O(1), otherwise
– Solution O(log2n)
Sorting an Array
• Rearranging array contents in
increasing or decreasing order
0 1 2 3 4
A 3 9 6 2 5
Sort in increasing order
0 1 2 3 4
A 2 3 5 6 9 How do we sort?
Courtesy Prof P R Panda CSE, IIT Dellhi 23
Simple Sorting Algorithm
A[0] A[i] A[i+1] A[N-1]
for in range(len(A)) :
k = position of min. element
between A [i] and A [N-1]
Swap A [i] and A [k]
Courtesy Prof P R Panda CSE, IIT Dellhi 24
Simple Sorting Algorithm
A[0] A[i] A[i+1] A[N-1]
for in range(len(A)) :
k = position of min. element
between A [i] and A [N-1] for j in range(i+1, len(A)):
Swap A [i] and A [k] if A[min_index] > A[j]:
min_index = j
t=A[i]
A[i]=A[k]
A[k]=t
Courtesy Prof P R Panda CSE, IIT Dellhi 25
Simple Sorting Algorithm
A[0] A[i] A[i+1] A[N-1]
Find Min for first time n elements: n-1 coparisons
Next time : n-2
.
.
up to 1
Total time = (n-1)+(n-2)+….+1=(n*(n-1))/2
O(n2)
Courtesy Prof P R Panda CSE, IIT Dellhi 26
