SPACE AND TIME TRADE-OFF

& SORTING BY COUNTING

INTRODUCTION

• We can say an algorithm is best when it takes less time for

execution and less storage space
• But in practical it is not possible
• There comes the space and time trade-ff algorithms.
• Space and time trade-off is a way of solving a problem
 In less time by using more memory (space)
 In little space by spending more time
• Choose based on the need
DIFFERENT APPROACHES
• Two approaches for space and time trade-off techniques
1. Input Enhancement: pre-process the problem’s input in whole or in
part and store the information. This information is used to solve the
problem. Algorithms which uses this approach are:
 Counting sort algorithm
 String matching algorithm
2. PreStructuring: pre-process the problem’s input to facilitate faster or
flexible access of data by using extra space. This approach is illustrated
by:
 Hashing
 Indexing with B-trees
ONE MORE

• Dynamic Programming is one of the design technique which is related to

space-for-time trade-off idea.
• In dynamic programming solutions of overlapping subproblems are stored
in a table. From these subproblem solutions we can obtain solution to
the given problem.
TWO COMMENTS

• These two resources (space & time) do not have to compete with each
other in all design situations.
 They can align to bring a solution that minimizes both time and space consumed.
 This can be done by choosing efficient data structure to represent a input, this in
turn leads to faster algorithm.
• Space & time trade-off is important in the area of data compression.
 In data compression size reduction is the goal rather than a technique for solving the
problem.
SORTING BY COUNTING

• It uses input-enhancement technique

• There are two sorting we are considering here
 Comparison Counting Sorting
 Distribution Counting Sorting
COMPARISON COUNTING SORTING
ALGORITHM
• The idea is to count
• For each element in the given list
• Count the total number of elements smaller than this element
• And store the result in a table
• The numbers in table indicate the positions of the elements in the
sorted list
• For eg: if the count of some element is 5 then it should be stored in
6th position (as array index starts from 0)
• Thus, we sort the list by copying its elements to their appropriate
positions in sorted list
ALGORITHM
ALGORITHM ComparisonSort(A)
// Sorts an array
//Input: An array A
//Output: Sorted array
for i <- 0 to n-1 do
count[i] <- 0 Initialize count
end-for
for i <- 0 to n-2 do
for j <- i+1 to n-1 do
if A[i] < A[j]
then If A[i]<A[j], is true
count[j] <- count[j] + 1 then increment count for jth element
else
count[i] <- count[i] + 1
end-if If A[i]<A[j], is not true
end-for then increment count for ith element
End-for
for i <- 0 to n-1 do
S[count[i]] <- A[i] Store sorted elements in array S
end-for
TRACING EXAMPLE

• Consider an array A = { 62, 31, 84, 96, 19, 47 } with six elements
• Let’s represent that in array format
A[]: 62 31 84 96 19 47
• For counting purpose we consider an array called count.
• Count array is initialized to 0

count[]: Intial 0 0 0 0 0 0
 TRACING
• In 1st pass we start comparing 1st element with all other
• 1st compare with next successive element
• If 1st element is greater than 2nd element than increase the count of 1st element
• Next compare 1st element with 3rd element
• If 1st element is less than 3rd element than increase the count of 3rd element
• And continue comparing till it reaches end
A[]: 62 31 84 96 19 47 • 62 > 31 so increase count of 62
• 62 < 84 so increase count of 84
• 62 < 96 so increase count of 96
• 62 > 19 so increase count of 62
• 62 > 47 so increase count of 62
count[]: Intial 0 0 0 0 0 0

count[]: 1st pass 3 0 1 1 0 0

 TRACING
• In 2nd pass we start comparing 2nd element with all other excluding 1st
element
• 2nd element is compared with next successive element
• If it is greater increase its count
• Else increase other compared element count
A[]: 62 31 84 96 19 47 • 31 < 84 so increase count of 84
• 31 < 96 so increase count of 96
• 31 > 19 so increase count of 31
• 31 < 47 so increase count of 47
count[]: Intial 0 0 0 0 0 0

count[]: 1st pass 3 0 1 1 0 0

count[]: 2nd pass 1 2 2 0 1

 TRACING
• In 3rd pass we start comparing 3rd element with all other excluding 1st & 2nd
element
• 3rd element is compared with next successive element
• If it is greater increase its count
• Else increase other compared element count
A[]: 62 31 84 96 19 47
• 84 < 96 so increase count of 96
• 84 > 19 so increase count of 84
• 84 > 47 so increase count of 84
count[]: Intial 0 0 0 0 0 0

count[]: 1st pass 3 0 1 1 0 0

count[]: 2nd pass 1 2 2 0 1

count[]: 3rd pass 4 3 0 1

 TRACING
• In 4th pass we start comparing 4th element with all other excluding 1st, 2nd &
3rd element
• 4th element is compared with next successive element
• If it is greater increase its count
• Else increase other compared element count
A[]: 62 31 84 96 19 47
• 96 > 19 so increase count of 96
• 96 > 47 so increase count of 96
count[]: Intial 0 0 0 0 0 0
count[]: 1st pass 3 0 1 1 0 0
count[]: 2nd pass 1 2 2 0 1
count[]: 3rd pass 4 3 0 1
count[]: 4th pass 5 0 1
 TRACING
• In 5th pass we start comparing 5th element with all other excluding 1st, 2nd , 3rd & 4th element
• 5th element is compared with next successive element
• If it is greater increase its count
• Else increase other compared element count

A[]: 62 31 84 96 19 47
• 19 < 47 so increase count of 47
Count[] Initial 0 0 0 0 0 0
Count[] 1st pass 3 0 1 1 0 0
Count[] 2nd pass 1 2 2 0 1
Count[] 3rd pass 4 3 0 1
Count[] 4th pass 5 0 1
Count[] 5th pass 0 2
 TRACING
• So, final state of count gives the position of the elements in sorted list
A[]: 62 31 84 96 19 47
Count[] Initial 0 0 0 0 0 0
Count[] 1st pass 3 0 1 1 0 0
Count[] 2nd pass 1 2 2 0 1
Count[] 3rd pass 4 3 0 1
Count[] 4th pass 5 0 1
Count[] 5th pass 0 2
Count[] Final 3 1 4 5 0 2

s[]: 19 31 47 62 84 96
ANALYSIS

• As all the different pairs of an n-element array is consider, time

complexity is n2
• Formally
• Basic operation is comparison A[i] < A[j].
• The number of times this basic operation is executed is:
n-2 n-1 n-2 n-2
• T(n) = ∑ ∑ 1 = ∑ [(n-1)-(i+1)+1] = ∑ (n-1-i) = n(n-1)/2 = n2
i=0 j=i+1 i=0 i=0
 DISTRIBUTION COUNTING SORT
ALGORITHM
• In this algorithm, the n input array elements is an integer in the range l to u.
• Where n is number of elements
• l is the lower bound or lowest value element
• u is the upper bound or highest value element
• For eg: A = { 4, 2, 2, 1, 3, 1},
 there are 6 elements.
 Lowest is 1.
 highest is 4.
• Then compute frequency of each of those values & store in array F[0..u-l]
• Then consider new array S[0..n-1] to hold sorted elements
• if the elements in A are equal to lowest value l are copied into first F[0] elements of
S. i.e from position 0 through F[0]-1
• Say from the eg array consider 1 its frequency is 2. it is copied to S from position 0
to 1.
DISTRIBUTION COUNTING SORT
ALGORITHM
• Next element of value l+1 are copied to positions from F[0] to
(F[0]+F[1])-1
• From eg array next element is 2. its frequency is 2. it is copied to S
from position 2 to 3
• And so on.
• This is accumulated sums of frequencies. Hence the distribution counting.
ALGORITHM
ALGORITHM DistributionCountingSort(A[0..n−1], l, u)
//Sorts an array of integers from a limited range by distribution counting
//Input: An array A[0..n−1]of integers between l and u (l≤u)
//Output: Array S[0..n−1]of A’s elements sorted in nondecreasing order
for j ←0 to u−l do
D[j]←0 initialize frequencies
end-for
for i ←0 to n−1 do
D[A[i]− l]←D[A[i]− l]+1 compute frequencies
end-for
for j ←1to u−l do
D[j]←D[j −1]+D[j] reuse for distribution
end-for
for i ←n−1downto 0 do
j ←A[i]− l
S[D[j]−1]←A[i]
D[j]←D[j]−1
end-for
return S
 EXAMPLE TRACING
• Consider an array A = { 13, 11, 12, 13, 12, 12 }
• Let us represent in array format
A[]: 13 11 12 13 12 12
• Array values are from the set {11, 12, 13}
• Frequency is number of times that element exists in the array
• Distribution is proper positions for last occurrence of the element in sorted
array
Array values 11 12 13
Frequencies 1 3 2
Distribution values 1 4 6

• Array element 12 is occurring 3 times. Distribution is 4 means last occurrence

of 12 will be in position 4 (i.e 3 as array index starts from 0)
TRACING
A[]: 13 11 12 13 12 12

• Process the input array from right to left.

• So, first consider last element of the array 12. it’s distribution value is 4, so place it
in 3 position(4-1) of array S.
• Then decrease 12’s distribution value by 1.

D[0..2] S[0..5]
11 12 13 A[0..5] S[0] S[1] S[2] S[3] S[4] S[5]
1 4 6 A[5] 12 12
A[4] 12
A[3] 13
A[2] 12
A[1] 11
A[0] 13
TRACING
A[]: 13 11 12 13 12 12

• consider last but one element of the array 12. it’s distribution value is 3, so place it
in 2 position(3-1) of array S.
• Then decrease 12’s distribution value by 1.

D[0..2] S[0..5]
11 12 13 A[0..5] S[0] S[1] S[2] S[3] S[4] S[5]
1 4 6 A[5] 12 12
1 3 6 A[4] 12 12
A[3] 13
A[2] 12
A[1] 11
A[0] 13
TRACING
A[]: 13 11 12 13 12 12

• consider element of the array 13. it’s distribution value is 6, so place it in 5

position(6-1) of array S.
• Then decrease 13’s distribution value by 1.

D[0..2] S[0..5]
11 12 13 A[0..5] S[0] S[1] S[2] S[3] S[4] S[5]
1 4 6 A[5] 12 12
1 3 6 A[4] 12 12
1 2 6 A[3] 13 13
A[2] 12
A[1] 11
A[0] 13
TRACING
A[]: 13 11 12 13 12 12

• consider element of the array 12. it’s distribution value is 2, so place it in 1

position(2-1) of array S.
• Then decrease 12’s distribution value by 1.

D[0..2] S[0..5]
11 12 13 A[0..5] S[0] S[1] S[2] S[3] S[4] S[5]
1 4 6 A[5] 12 12
1 3 6 A[4] 12 12
1 2 6 A[3] 13 13
1 2 5 A[2] 12 12
A[1] 11
A[0] 13
TRACING
A[]: 13 11 12 13 12 12

• consider element of the array 11. it’s distribution value is 1, so place it in 0

position(1-1) of array S.
• Then decrease 11’s distribution value by 1.

D[0..2] S[0..5]
11 12 13 A[0..5] S[0] S[1] S[2] S[3] S[4] S[5]
1 4 6 A[5] 12 12
1 3 6 A[4] 12 12
1 2 6 A[3] 13 13
1 2 5 A[2] 12 12
1 1 5 A[1] 11 11
A[0] 13
TRACING
A[]: 13 11 12 13 12 12

• consider element of the array 13. it’s distribution value is 5, so place it in 4

position(5-1) of array S.
• Then decrease 13’s distribution value by 1.

D[0..2] S[0..5]
11 12 13 A[0..5] S[0] S[1] S[2] S[3] S[4] S[5]
1 4 6 A[5] 12 12
1 3 6 A[4] 12 12
1 2 6 A[3] 13 13
1 2 5 A[2] 12 12
1 1 5 A[1] 11 11
0 1 5 A[0] 13 13
TRACING
A[]: 13 11 12 13 12 12

• Final sorted array S

D[0..2] S[0..5]
11 12 13 A[0..5] S[0] S[1] S[2] S[3] S[4] S[5]
1 4 6 A[5] 12 12
1 3 6 A[4] 12 12
1 2 6 A[3] 13 13
1 2 5 A[2] 12 12
1 1 5 A[1] 11 11
0 1 5 A[0] 13 13
11 12 12 12 13 13
ANALYSIS

• Time complexity of this algorithm is linear i.e n as it makes just two

consecutive passes through its input array.
0
• T(n) = ∑ 1 = (n-1-0+1) = n
i=n-1
Thank you