2.2 Space Complexity 2 )example Sequential Search(program 2.1) Template<class t> int Sequential Search(T all, const T&x, int n) int 1 for(i=0;i<n&&a[i]!x,i++); If(i==return return 1
2.2 Space Complexity 2)example: • Sequential Search (program 2.1) Template<class T> int SequentialSearch(T a[], const T&x, int n) { int i; for(i=0; i<n&&a[i]!=x; i++) ; If(i= =n)return –1; return i; }
2.2 Space Complexity Total data space 12 bytes( x, i, a[1],,-1, n, each of them cost 2 bytes)
2.2 Space Complexity Total data space: 12 bytes( x,i,a[i],0,-1,n, each of them cost 2 bytes) S(n)=0
2.2 Space Complexity Recursive code to add a[0 n-1(Program 1.9) Template <class t> T Rsumtal l, int n) f if(n>0 return Rsum (a, n-1)+an-1 return 0
2.2 Space Complexity • Recursive code to add a[0:n-1] (Program 1.9) Template <class T> T Rsum(T a[ ], int n) { if ( n>0 ) return Rsum(a, n-1) + a[n-1]; return 0; }
2.2 Space Complexity Recursion stack space formal parameters: a(2 byte), n (2 byte) return address(2 byte) Depth of recursion: n+1 SSum(n)=6(n+1)
2.2 Space Complexity Recursion stack space: formal parameters : a (2 byte), n(2 byte) return address(2 byte) Depth of recursion: n+1 SRsum(n)=6(n+1)
2.3 Time complexity The time taken by a program p is t(p) T(p=compile timetrun time The compile time does not depend on the instance characteristics The run time is denoted by t(instance characteristics) D)operation counts identify one or more key operations and determine the num ber of times these are performed
2.3 Time complexity The time taken by a program p is T(p) T(p)=compile time+run time The compile time does not depend on the instance characteristics The run time is denoted by tp (instance characteristics) 1)operation counts identify one or more key operations and determine the number of times these are performed