Algorithm Making

Computer Programming II (TA C252, Lect 9_10)

Today’s Agenda 

Efficiency & Complexity 

Efficiency in Programming 

Good Programming Practices    

 

Avoid redundant computation Avoid unnecessary array references Inefficiency due to late termination Early detection of desired output conditions

Issues Order of Complexity

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

2

Avoid redundant computations x=0;a=5;b=2;

x=0;a=5;b=2; for(i=0;i
Friday, September 4, 2009

const1=a*a*a+c; const2=b*b; for(i=0;i
Biju K Raveendran@BITS Pilani.

3

Avoid unnecessary array references p=0; for(i=1;ia[p]) p=i; } max=a[p];

Friday, September 4, 2009

p=0; max=a[0]; for(i=1;imax) { p=i; max=a[i]; } } Biju K Raveendran@BITS Pilani.

4

Inefficiency due to late termination for (i=0;i
Friday, September 4, 2009

for (i=0;ix) return NOT FOUND; i++; } return NOT FOUND;

Biju K Raveendran@BITS Pilani.

5

Early detection of desired output sorted=0; condition i=0; while ( ( i < N ) && ( sorted = = 0) ) { j=0; sorted=1; while ( j < (N – i – 1) ) { if(a[j]> a[(j+1)]) { temp=a[j]; a[j]=a[(j+1)]; a[(j+1)]=temp; sorted=0; } j++; } i++; }

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

6

What is Efficiency ?  

Efficiency – Design & Implementation issue. Resources  



CPU Time Storage

Resource Usage 

Measured proportional to (input) size

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

7

Design Level Measurement 

Machine-independent measurement needed  

Often referred to as “algorithmic complexity” Individual statement considered as “unit” time 



Not applicable for function calls and loops

Individual variable considered as “unit” storage 

Not applicable for arrays (or other collections)

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

8

Order of complexity [1] 

Example 1 (Y and Z are input) X = 3 * Z; X = Y + X; // 2 units of time and 1 unit of storage

// Constant Unit of time and Constant Unit of storage

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

9

Order of complexity [2] 

Example 2 (a and N are input) j = 0; while (j < N) do a[j] = a[j] * a[j]; b[j] = a[j] + j; j = j + 1; endwhile; // 3N + 1 units of time and N+1 units of storage // time units prop. to N and storage prop. to N

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

10

Order of complexity [3] 

Example 2 (a and N are input) j = 0; while (j < N) do k = 0; while (k < N) do a[k] = a[j] + a[k]; k = k + 1; endwhile; b[j] = a[j] + j; j = j + 1; endwhile; // time prop. to N2 and storage prop. to N

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

11

Motivation for Order Notation log2N

N

N2

N3

2N

1

2

4

8

4

3.3

10

102

103

>103

6.6

100

104

106

>1025

9.9

1000

106

109

>10250

13.2

10000

108

1012

>102500

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

12

Motivation for Order Notation 

Examples •

100 * log2N < N

•

70 * N + 3000 < N2 for N > 100 105 * N2 + 106 * N < 2N for N > 26

•

Friday, September 4, 2009

for N > 1000

Biju K Raveendran@BITS Pilani.

13

Order Notation Asymptotic Complexity g(n) is O(f(n)) if there is a constant c such that g(n) <= c(f(n)) i.e. limn∝ (g(n) / f(n)) = c and c<>0 

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

14

Linear Search - Complexity function search(X, A, N) j = 0; while (j < N) if (A[j] == X) return j; j++; endwhile; return “Not_found”;

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

15

Linear Search - Complexity 

Time Complexity: “if” statement introduces possibilties   

Best-case: O(1) Worst case: O(N) Average case: ???

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

16

Linear Search - Complexity 

Average case • •

•

Assume elements in A are randomly distributed. Then for N different cases, 1, 2, 3, … N are equally possible values of number of iterations. So expected value: (1 + 2 + … + N) / N

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

17

Linear Search - Complexity 

Average case (Σi=0 to N I)/N = (N(N+1)/2 )/N = (N+1)/2 is O(N)



Space Complexity O(1)

i.e. constant space.

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

18

Binary Search Algorithm low = 0; high = N-1; while (low <= high) do mid = (low + high) /2; if (A[mid] = = x) return x; else if (A[mid] < x) low = mid +1; else high = mid – 1; endwhile; return Not_Found;

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

19

Binary Search - Complexity  

Often not interested in best case. Worst case:    

Loop executes until low <= high Size halved in each iteration N, N/2, N/4, … 1 How many steps ?

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

20

Binary Search - Complexity 

Worst case: 

K steps such that 2K = N i.e. log2N steps

is O(log(N)) 

Best case: 

O(1)

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

21

Binary Search - Complexity 

Average Case: 1 + 2 + 2 + 3 + 3 + 3 + 3 + … (upto logN steps) Sigma((i+1)*2i) for i = 0 to log2N Evaluates to O(log N) 1 element can be found with 1 comparison 2 elements  2 4 elements  3 Above Sum =sum over all possibilities



Space Complexity is O(1)

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

22

xy - Complexity 

Assume y = 2k  



k steps in the iteration. Complexity is O(k)

General case Sigma(log22k) for k = 1 to log2 y log (Product(2k)) for k =1 to log2y log(y)

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

23

Complexity Example: xy 

Discuss if time permits

Friday, September 4, 2009

Biju K Raveendran@BITS Pilani.

24