Step-Count Method II

Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 1 of Science for Women
Example 3: Find the space and the time complexities for the following function
using step count method.
Function sum2( a: ElemList ; n : integer) : real;
var k : integer;
s: real;
Begin
s := 0;
For k := 1 to n do
s := s + a[k];
sum1 := s;
End;
Solution:
Space complexity: The function sum2 requires six spaces (four of type integer
and two of type real) to store the values of each ( n, k, s, sum2,and constants
0, 1). The space needed by a is the space needed by variables of type
ElemList. This is equal to MaxSize. We see that the space needed by function
sum2 is
Ssum2(n) = 16 Bytes + Maxsize
Or Ssum2(n) ? n
Note: if we change the formal parameter a from value to reference ( or Var),
only the address of the actual parameter gets transferred to the function and
the space needed by the function is independent of instance characteristics
(n), in this case Ssum2(n) = 0.
Time complexity:
Tsum2(n) = 1 + (n+1) + n + 1 = 2n + 3
Example 4: Find the space and the time complexities for the following function
using step count method.
Function rsum( a: ElemList ; n : integer) : real;
Begin
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 2 of Science for Women
If n = 1 then rsum := a[1]
Else rsum := a[n] + rsum( a, n-1);
End;
e.g., the recursion rsum(a, 3)
when n= 3 &
a[1..3] = (7, 5, 3)
Solution:
Space complexity: each call to rsum requires ( 10 Bytes + MaxSize) of space
( including 2 Bytes for n, 2 Bytes for return address, 2 Bytes for constant 1, 4
Bytes for rsum, and MaxSize of type ElemList for a).
The Depth of Recursion =
????? ?????????????? ???????? ???? ?????
?????????? ???????????????????? - ????? ???????????????? ????????
???? ????? ???????? ???????????????????? +1
The Depth of Recursion = n – 1 + 1 = n
Srsum(n) = n * ( 8 Bytes + MaxSize )
Or Srsum(n) ? n * ( 8 Bytes + n )
Note: if we make a a variable parameter, then each call to rsum require only
10 Bytes ( including 2 Bytes for n, 2 Bytes for return address, 4 Bytes for rsum,
and 2 Bytes for a). The overall space that needed by rsum is
Srsum(n) = 10 Bytes * n
n is 3
3 = 1 False
rsum := 3 + rsum(a, 2)
n is 2
2 = 1 False
rsum := 5 + rsum(a, 1)
n is 1
1 = 1 True
rsum := 7
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 3 of Science for Women
Time complexity:
2 if n = 1
Trsum(n) =
MaxSize + 1 + trsum ( n – 1 ) if n > 1
We can solve the previous recurrence relation by using Iterative Substitution
method
trsum (n) = MaxSize + 1 + trsum ( n – 1 )
= MaxSize + 1 + (MaxSize + 1 + trsum ( n – 2 ))
= 2(MaxSize + 1) + trsum ( n – 2 )
= 2(MaxSize + 1) +( MaxSize + 1 + trsum ( n – 3 )
= 3(MaxSize + 1) + trsum ( n – 3 )
...
...
= K(MaxSize + 1) + trsum ( n – K )
Suppose K = n - 1
= ( n – 1) (MaxSize + 1) + trsum ( n – ( n – 1) )
= ( n – 1) (MaxSize + 1) + trsum ( 1 )
trsum (n) = ( n – 1) (MaxSize + 1) + 2
Note: if we change the formal parameter (a) from value to reference
parameter, then the step count for trsum as follow:
trsum (n) = 2n + 2
Example 5: Find the space and the time requirements for the following
procedure using step count method.
Procedure Add(var A,B,C : Matrix; m,n : integer);
var i, j : integer;
Begin
For i:= 1 to m do
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 4 of Science for Women
For j:= 1 to n do
C[i,j] := A[i,j] + B[i,j];
End;
Solution:
Space requirement: the procedure Add need 2 Bytes for each of A, B, C, and
2 Bytes for each of m, n, i, j and 2 Bytes for constant 1. the total space that
needed by procedure Add is (16 Bytes). We see that the space needed by
procedure Add is independent of the instance characteristics (m, n).
Consequently, SAdd(m,n) = 0
Time requirement:
Tadd(n,m) = 2mn + 2m + 1
Note: from this analysis we see that if m > n, then it is better to interchange
the two for statements in procedure Add above. If this is done, the step count
become Tadd(n,m) = 2mn + 2n + 1
Example 6: Write a program for Fibonacci numbers Fn that defined as follow:
F0=0, F1=1, and Fn = Fn-1 + Fn-1 for all n ? 2. Analyze this program to find the
space and the time requirements using step count method.
Solution:
Program fibo;
var f1, f2, fn, n, i : integer;
begin
readln(n);
if n <= 1 then writeln(n)
else begin
f1 := 0; f2 := 1;
For i:= 2 to n do
Begin
fn := f1 + f2 ;
f1 := f2;
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 5 of Science for Women
f2 := fn;
end;
writeln(fn);
end;
end;
Space requirement: the program fibo needs 2 Bytes for each (f1, f2, fn, n, i)
and 2 Bytes for each of constants (0, 1, 2). We see that the space needed by
program fibo (16 Bytes) is independent of the instance characteristics (n).
Consequently, Sfibo(n) = 0
Time requirement:
3 if n ? 1
Tfibo(n) =
4n + 2 if n > 1
Example 7: compare between the following two codes (A and B) using step
count method.
The code B is better than the code A
Example 8: write a procedure for computing the prefix averages for a
sequence of numbers as defined below: the array x used to store n integer
elements, it is required the array a, where the element ai represent the
average of element values from x1 to xi, i= 1, 2, …, n, and ???? =
? ????
??
??=1
?? .
The code A
i := 1; 1
while I <= n do n + 1
begin
x := x + 1; n
i := i + 1; n
end;
T = 3n + 2
The code B
i := 1; 1
repeat 0
x := x + 1; n
i := i + 1; n
until ( I > n); n
T = 3n + 1
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 6 of Science for Women
analyze the procedure to find the space and time requirements using stepcount
method.
Procedure PrefixAverage(x : ElemList; var a: ElemList; n: integer);
var i, j, s : integer;
begin
for i:= 1 to n do
begin
s := 0;
for j:= 1 to i do
s := s + x[ j ];
a[i] := s / i ;
end;
end;
Solution:
Space requirement: the procedure PrefixAverage need space as follow: 2
Bytes for each of (a, n, i, j, s, and constants 0,1) and MaxSize of type ElemList
for x.
S PrefixAverage (n)= 12 Bytes + MaxSize
Or S PrefixAverage (n) ? n
Time requirement:
?????? ???????????? ???? ??????????
= (|?????? ?????????????? ?????????? ???? ?????????????? ???????? ? ?????? ?????????????? ?????????? ???? ?????????????? ????????| + ??) + ??
For i \ n + 1
S:=0 \ n
For j \ ? (|?? ? 1| + 1) ?? ??
=1 + 1 ? ? (?? + 1) ?? ??
=1 ?? ?? ?? ??
=1 + ? 1 = ??(??+1)
??
?? ??
=1 + ??
s := s + x[ j ] \ ??(??+1)
??
a[i] := s / i \ n
T PrefixAverage (n)= (n+1) + (n) + (??(??+1)
?? + ??) + (??(??+1)
?? ) + (n)
= n2 + 5n + 1
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 7 of Science for Women
Homework:
1. Analyze the following functions to find the time complexity using stepcount
method.
Function mystery(n:integer) : integer;
var r, i, j, k: integer;
Begin
r := 0;
For i:= 1 to n-1 do
For j:= i+1 to n do
For k := 1 to j do
r := r + 1
Mystery := r;
End;
2. Analyze the following functions to find the time complexity using stepcount
method.
Function pesky(n:integer) : integer;
var r, i, j, k: integer;
Begin
r := 0;
For i:= 1 to n do
For j:= 1 to i do
For k := i to i+j do
r := r + 1
pesky := r;
End;
3. Analyze the following functions to find the time complexity using stepcount
method.
Function pestiferous(n:integer) : integer;
var r, i, j, k, l: integer;
Begin
r := 0;
For i:= 1 to n do
For j:= 1 to i do
For k := j to i+j do
For l := 1 to i+j-k do
r := r + 1
pestiferous := r;
End;
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 8 of Science for Women
4. Analyze the following functions to find the time complexity using stepcount
method.
Function con(n:integer) : integer;
var r, i, j, k: integer;
Begin
r := 0;
For i:= 1 to n do
For j:= i+1 to n do
For k := i+j-1 to n do
r := r + 1
con := r;
End;
Notes:
1- The benefit of analysis of algorithms is
a) Predicting the behavior of algorithm when increasing the number
of inputs.
b) The Comparing between two algorithms.
2- We can compute the time complexity during the program as follow:
We can determine the number of steps needed by a program to solve a
particular problem instance by introducing a new variable , count into the
program. This is a global variable with initial value 0. This is done so that
each time a statement in the original program is executed, count is
incremented by the step count of that statement. For example:
Function sum(a: ElemList; n: integer): real;
var s: real; i: integer;
Begin
s := 0;
count := count +1; { for assignment }
For i:= 1 to n do
Begin
count := count +1; { for For }
s:= s + a[i];
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 9 of Science for Women
count := count +1; { for assignment }
end;
count := count +1; { for last time of For }
sum:= s;
count := count +1; { for assignment }
end;