Scribd
Upload
93 views5 pages

Step Count Method for Time Complexity

The document discusses the step-count method for estimating time complexity in algorithm design, detailing how to account for various types of statements in a program. It categorizes statements such as comments, declarations, expressions, iterations, and conditionals, assigning step counts based on their characteristics. Examples illustrate how to calculate space and time complexities for specific functions using this method.

Uploaded by

hasinig883
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
93 views5 pages

Step Count Method for Time Complexity

The document discusses the step-count method for estimating time complexity in algorithm design, detailing how to account for various types of statements in a program. It categorizes statements such as comments, declarations, expressions, iterations, and conditionals, assigning step counts based on their characteristics. Examples illustrate how to calculate space and time complexities for specific functions using this method.

Uploaded by

hasinig883
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithm Design And Analysis Asst. Prof.

Ali Kadhum Idrees

[Link]. Step-Count Method:


As noted in some of the examples on operations count, the operation-
count method of estimating time complexity omits accounting for the time
spent on all but the chosen operations. In the step-count method, we attempt
to account for the time spent in all parts of the program/function. The step-
count is a function of the instance characteristics (e.g., the number of inputs,
the number of outputs, the magnitudes of inputs and outputs). The number of
steps is computed as a function of some subset of these.
The step-count method is a measure to estimate the time complexity
where the number of steps any program statement is to be assigned depends
on the nature of that statement. The following discussion considers the various
statement types that can appear in a Pascal program and states the
complexity of each in terms of the number of steps.
 Comments: comments are nonexecutable statements and have a step
count of zero.
 Declarative statements: this includes all statements of type const, label,
type, and var. these counts as zero steps as these are either
nonexecutable or their cost may be lumped into the cost of invoking the
procedure/function they are associated with.
 Expressions and assignment statements: most expressions have a step
count of one. The exceptions are expressions that contain function calls.
In this case, we need to determine the cost of invoking the functions.
This cost can be large if the function employ many-element value
parameters as the values of all actual parameters need to be assigned
to the formal parameters. This is discussed future under procedure and
function invocation. When the expression contains functions, the step
count is the sum of the step counts assignable to each function
invocation.

Department of Computer Science 1


College of Science for Women
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees

The assignment statement <variable> := <expr> has a step count


equal to that of <expr> unless the size of <variable> is a function of the
instance characteristics. In this later case, the step count is the size of
<variable> plus the step count of <expr>. For example, the assignment
a := b where a and b are of type ElementList has a step count equal to
the size of ElementList.
 Iteration statements: this class of statements includes the For, While,
and Until statements. We shall consider the step counts only for the
control part of these statements. These have the form:
For i:= <expr> to <expr> do
For i:= <expr> downto <exprl> do
While <expr> do
Until <expr>;
Each execution of the control part of a while and until statement will be
given a step count equal to the number of step counts assignable to
<expr>. The step count for each execution of the control part of a For
statement is one, unless the counts attributable to <expr> and <exprl>
are a function of the instance characteristics. In this latter case, the first
execution of the control part of the For has a step count equal to the
sum of the counts for <expr> and <exprl> (note that these expressions
are computed only when the loop is started). Remaining executions of
the For have a step counts of one.
 Case statement: this statement consists of a header followed by one or
more sets of condition and statement pairs.
Case <expr> of
Cond1: <statement1>
Cond2: <statement2>
.
.
.
Else: <statement>
End;

Department of Computer Science 2


College of Science for Women
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees

The cost of the header Case <expr> of is given a cost equal to that
assignable to <expr>. The cost of each following condition-statement
pair is the cost of this condition plus that of all preceding conditions plus
that of this statement.
 If-Then-Else statements: the if-then-else statement consists of three
parts:
If <expr>
Then <statement 1>
Else <statement 2>
Each part is assigned the number of steps corresponding to <expr>,
<statement 1>, and <statement 2> respectively, note that if the else
clause is absent, then no cost is assigned to it.
 Procedure and Function invocation: all invocations of procedures and
functions count as one step unless the invocation involves value
parameters whose size depends on the instance characteristics. In this
latter case, the count is the sum of the size of these value parameters. In
case the procedure/ function being invoked is recursive, then we must
also consider the local variable in the procedure or function being
invoked. The sizes of local variables that are characteristic dependent
need to be added into the step count.
 Begin, End, With, and Repeat statements: each With statement counts
as one step. Each Begin, End, and Repeat statement counts as zero
steps.
 Procedure and function statements: these count as zero steps as their
cost has already been assigned to the invoking statements.
 Goto statement: this has a step count of one.
Example 1: Find the space and the time complexities for the following function
using step count method.
Function Abc(a, b, c : real) : real;
Begin

Department of Computer Science 3


College of Science for Women
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees

Abc := a + b + b * c + (a + b – c) / (a + b) + 4;
End;
Solution:
Space complexity: One word of type real is a adequate to store the values of
each of a, b, c, 4, and Abc. We see that the space needed by function Abc is
independent of the instance characteristics. Consequently,
SAbc(a, b, c) = 0
Time complexity:
TAbc(a, b, c) = 1

Example 2: Find the space and the time complexities for the following function
using step count method.
Function sum1(n : integer) : integer;
var k, s : integer;
Begin
s := 0;
For k := 1 to n do
s := s + k;
sum1 := s;
End;
Solution:
Space complexity: The function sum1 requires six words of type integer to
store the values of each ( n, k, s, sum1, and constants 0, 1). We see that the
space needed by function sum1 (12 Bytes) is independent of the instance
characteristics. Consequently,
Ssum1(n) = 0
Time complexity:
Tsum1(n) = 1 + (n+1) + n + 1 = 2n + 3

Department of Computer Science 4


College of Science for Women
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees

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

Department of Computer Science 5


College of Science for Women

Common questions

Powered by AI

Recursive procedures need additional consideration in step-count analysis because each recursion level potentially alters the size of local variables, especially when these sizes are instance characteristic dependent. The recursive calls must account for storing new local variable instances, potentially increasing the step count significantly .

When invoking functions with value parameters in the step-count method, the step count must include the size of these value parameters if it depends on instance characteristics. The complexity increases when large parameter values are involved, impacting the overall step count. Additionally, if the function is recursive, the size of local variables dependent on instance characteristics must also be considered in the step count .

Space complexity in the step-count method is determined by the variable storage requirements independent of instance characteristics. For example, function sum1 calculates space needed for each integer and constant, leading to a calculation of 12 bytes, which is independent of the instance characteristics. In function sum2, if parameter 'a' is changed to reference, space complexity similarly becomes independent of instance characteristics .

Changing a parameter from value to reference in the step-count method affects space complexity because reference parameters only pass the address of the variable, not the entire data. This reduces the space needed within a function, as seen in the case of function sum2, where changing parameter 'a' from value to reference eliminates the dependency on instance characteristics for space complexity .

Recursion in the step-count method adds complexity as it requires calculating the size and cost of local variables for each recursive call. If local variables are dependent on instance characteristics, these factors must be included in the step-count calculation for recursive procedures and functions, necessitating deeper analysis of recursive execution paths and variable storage needs .

Expressions containing function calls in the step-count method have a step count that is the sum of the step counts for each function invocation. This is because invoking a function can significantly increase complexity, particularly with many-element value parameters requiring assignments to formal parameters .

For 'for' statements, the first execution has a step count equal to the sum of the expressions within the loop, especially if these expressions depend on instance characteristics. Further executions count as one step each. 'While' and 'until' statements consider the step count assignable to the controlling expression, calculated for each execution of the control part .

Non-executable statements like comments and declarative statements, which include constant, label, type, and variable declarations, have a step count of zero. Their cost is either non-existent or merged into related procedure/function costs, ensuring they do not impact time complexity calculations using the step-count method .

The step-count method provides a more accurate estimation of time complexity by accounting for the time spent on all parts of the program, including comments, declarative statements, assignments, iteration, and more, rather than only focusing on selected operations. This method considers the number of steps as a function of the instance characteristics, thus offering a comprehensive view of all potential executions in the program .

Conditional statements like 'if-then-else' and 'case' statements contribute to the step count by adding the complexity of evaluating conditions and executing corresponding actions. Each condition and statement pair in a 'case' statement gets a cost dependent on condition evaluation plus preceding conditions. In 'if-then-else', every part has its step count based on the expressions and statements involved .

You might also like