Module I CS201 – Data Structures(KTU)

Module I
• System Life Cycle
• Algorithms
• Performance Analysis
o Space Complexity
o Time Complexity
• Asymptotic Notation
• Complexity Calculation of Simple Algorithms

SYSTEM LIFE CYCLE (Explain system life cycle:10 marks)

• Good programmers regard large scale computer programs as systems that contain many
complex interacting parts. (Systems: Large Scale Computer Programs.)
• As systems, these programs undergo a development process called System life cycle.( SLC
: Development Process of Programs)
• The system life cycle is a series of stages that are worked through during the development
of a new information system.
• A lot of time and money can be wasted if a system is developed that doesn’t work properly
or do exactly what is required of it.
5 Phases of system life cycle
1. Requirements phase
2. Analysis phase
3. Design phase
4. Refinement and coding phase
5. Verification phase
[Link] phase
• All programming projects begin with a set of specifications that defines the purpose of
that program.
• Requirements describe the information that the programmers are given (input) and the
results (output) that must be produced.
• Frequently the initial specifications are defined vaguely and we must develop rigorous
input and output descriptions that include all cases.
[Link] phase
• In this phase the problem is break down into manageable pieces.
• Generate diagrams that are used to design the system
• Several alternate solutions to the programming problem are developed and compared
during this phase
• There are two approaches to analysis:- (4 marks)
i. Bottom-up approach
ii. Top-down approach
Bottom up approach
➢ Bottom-up approach is an older, unstructured strategy that places an early emphasis on
coding fine points.
➢ Since the programmer does not have a master plan for the project, the resulting program
frequently has many loosely connected, error ridden segments.
Module I CS201 – Data Structures(KTU)

➢ It is like developing a building from generic blueprint.

Top down approach
➢ Top-down approach is a structured approach divide the program into manageable
segments.
➢ This phase generates diagrams that are used to design the system

[Link] Phase

• This phase continues the work done in the analysis phase.

• The designer approaches the system from the perspectives of both data objects that the program
needs and the operations performed on them.
• Ex: Designing a scheduling system for university
Data objects: Students, courses, professors etc
Operations: insert, remove search etc.. [Link] might add a course to the list of university
courses, search for the courses taught by some professor etc.
• The first perspective leads to the creation of abstract data types while the second requires the
specification of algorithms and a consideration of algorithm design strategies
• Since abstract data types and algorithm specifications are language independent, we must
specify the information required for each data object and ignore coding details.
Ex: Student object should include name, phone number, social security number etc.
However, we would not yet pick a specific implementation for the list of students

4. Refinement and Coding Phase

• In this phase we choose representations for data objects and write algorithms for each operation
on them.
• Data objects representation can determine the efficiency of the algorithm related to it. So we
should write algorithms that are independent of data objects first.
• Frequently we realize that we could have created a much better system. (May be we realize that
one of our alternate design is superior than this). If our original design is good, it can absorb
changes easily.

[Link] Phase (What is significance of verification in lifecycle?:4marks)

This phase consists of

• developing correctness proofs for the program

• Testing the program with a variety of input data
• Removing errors

Correctness of proof
• Program can be proven correctly using proof(like mathematical theorem)
• Proof are very time consuming and difficult for develop for large program
• Scheduling constraints presents the development of complete set of proofs for a
larger system
• However selecting the algorithm that have been proven correct can reduce the
number of errors
Module I CS201 – Data Structures(KTU)

Testing
• Testing can be done only after coding
• Testing require work code and set of test data
• Test data should be chosen carefully so that it include all possible scenarios
• Good test data should verify that every piece of code correctly
• Eg: If our program contain a switch statement, our test data should lie chosen so that
we can check each case within switch statement
Error removal
• If not done properly ,the correctness of proof and system test will indicate erroneous
code
• Removal of errors depend on design and code
• While debugging large undocumented programs each corrected error possibly
generate several new errors
• Debugging a well-documented program that is divided into autonomous units that
interact through parameters is far easier.
• This is especially true if each unit is tested separately and then integrated into a
system

ALGORITHM (Difference between algorithm and pseudocode 4marks)

• An algorithm is a finite set of instructions that accomplishes a particular task.

• It is a step by step procedure to solve the problem.
• It is the simplest representation of the program in our own language.
• An algorithm can be abstract or quite detailed.
• It is not dependent on any programming language, so it is easy to understand for
anyone evenwithout programming knowledge.
• Every step in an algorithm has its own logical sequence so it is easy to debug.
• Algorithm does not follow any rules.

➢ Properties of an Algorithm (Different criterion an algorithm should satisfy-

3marks)

1) Input: Zero or more inputs are externally supplied.

2) Output: At least one output is produced.
3) Definiteness: Each instruction is clear and unambiguous.
“add 6 or 7 to x” , “compute 5/0” etc. are not permitted.
4) Finiteness: The algorithm terminates after a finite number of steps.
5) Effectiveness: Every instruction must be very basic so that it can be carried out by
a person using only pencil and paper in a finite amount of time. It also must be
feasible.

PSEUDO CODE

• Pseudo code is an implementation of an algorithm

• It is a more formal representation than an algorithm
• Each step is very closer to the actual programming language
Module I CS201 – Data Structures(KTU)

• Acts as a bridge between the program and the algorithm.

• Don’t make the pseudo code abstract.
• Don’t be too generalized
• The main goal of a pseudo code is to explain what exactly each line of a program should
do, hence making the code construction phase easier for the programmer.
• Also works as a rough documentation, so the program of one developer can be
understood easily when a pseudo code is written out. In industries, the approach of
documentation is essential. And that's where a pseudo-code proves vital.

Example : Consider the linear search in an array, the algorithm can be written as below;

1) Start from the first element of the array.

2) Compare the current element with the target value T.
3) If the current element equals T, return the current index.
4) If the current element does not equal T, move to the next element and repeat step 2.
5) If the end of the array is reached and the target value T is not found, return -1.

The pseudocode for the same problem can be written as below;

function linearSearch(A, n, T):

for i from 0 to n-1:
if A[i] = = T:
return i
return -1

From the above example we can see that pseudocode act as a bridge between algorithm and
actual program in a specific language.

RECURSIVE ALGORITHMS

• A recursive function is a function that is defined in terms of itself

• An algorithm is said to be recursive if the same algorithm is invoked in the body
• Two types of recursive algorithms
➢ Direct Recursion: An algorithm that calls itself is direct recursive.
➢ Indirect Recursion: An algorithm A is said to be indirect recursive if it
calls another algorithm , which in turn calls A

PERFORMANCE ANALYSIS (How the performance of an algorithm is evaluated:5 marks)

• When we have more than one algorithm to solve a problem, we need to select the best
one. Performance analysis helps us to select the best algorithm from multiple algorithms
to solve a problem.
• Performance analysis means analysis of performance of an algorithm before execution
Module I CS201 – Data Structures(KTU)

• Performance analysis depends on Space Complexity and Time Complexity

➢ Space Complexity (3marks)

➢ The space complexity of an algorithm is the amount of memory it needs to run to

completion

➢ Space Complexity = Fixed Part + Variable Part

S(P) = c + S P (I) , Where,

▪ P is any algorithm/program and I is an instance
▪ S(P): Total space required
▪ c : Fixed space
▪ Sp(I): Variable [Link], space required at a
particular instance I

Fixed Part:

▪ It is independent of the characteristics of the inputs and outputs.

▪ Eg:
o Instruction space(i.e., space for the code)
o space for simple variables and fixed-size component variables
o space for constants

eg:Float abc(float a,b,c)

{
Return a+b+b*c+(a+b-c)/(a+b)+4.00
}
• We have function abc, which accept 3 simple variables as input and
returns a simple value as output
• According to the classification give, the function has only fixed
space requirements
So, S abc (I) =0
Variable part:

▪ It is dependent on the characteristics of the inputs and outputs.

▪ Eg:
o Space needed by component variables whose size is dependent on
the particularproblem instance being solved
o Space needed by referenced variables
o Recursions stack space.
Module I CS201 – Data Structures(KTU)

Space complexity calculation :

Example 1

Algorithm Sum(A,n)
{
s=0
for i=0 to n-1 do
s = s + A[i] return s
}

Example 2

Algorithm mAdd (a,b,c,m,n)

{
for i=1 to m do
for j=1 to n do
c[i,j] = a[i,j] + b[i,j];
}

Space Complexity Calculation of recursive algorithms

➢ Generally the space required for recursive call can be calculated as

S =Total no of recursive calls *space required for one recursive call

➢ Space required for one recursive call includes the space for parameters, space for local
variables and space for return address. Because for each recursive call, this much
Module I CS201 – Data Structures(KTU)

memory space is reserved in the stack

Example 1

Algorithm RSum(a,n)
{
if(n<=0)
return 0;
else
return a[n] + RSum(a,n-1)
}

S =Total no of recursive calls *space required for one recursive call

➢ Here the recursion goes from n down to 0, making n+1 recursive calls.
➢ Space required for on recursive call
= Space for parameters + Space for local variables + Space for return address
➢ Space for parameters: Two parameters
i. a :1(Here we assume that only the reference to the array is passed
in a recursive call , not the entire array, so memory requirement is
taken as 1 unit)
ii. n:1
➢ Space for local variables: No local variables
➢ Space for return address: 1

For each recursive call the amount of stack required is 3

Space complexity = 3(n+1)

Example 2

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)

➢ Here there is two recursive functions inside the algorithm .

➢ In that case ,
o We take number of recursive calls by each function and maximum of
them will be taken for space calculation .
➢ Here first recursive function calls n times ( goes from n to 1)and second one will
be obviously less than that
Module I CS201 – Data Structures(KTU)

So maximum number of recursive calls for a function is n

Space per call:

Return address :1
Parameters :1

Total space is : n*2=2n

➢ Time Complexity

• Time complexity is the amount of time it needs to run to completion

• The time, T(P) taken by a program, P, is the sum of its compile time and its run
(or execution) time.
• The compile time is similar to the fixed space component since it does not
depend on the instance characteristics.
• In addition, once we have verified that the program runs correctly, we may run
it many times without recompilation.
• Consequently, we are really concerned only with the program’s execution
time, Tp.
• Obtaining detailed estimate of running time is rarely worth the effort .(If we
must know the running time, the best approach is to use the system clock to time
the program. )
• So we try to find the total steps required to complete the program, which is
known as total step count of the program and assume that each step takes a
fixed time.
• A program step is a syntactically or semantically meaningful program segment
whose execution time is independent of the instance characteristics.

❖ Note that the amount of computing represented by one program step may be
different from that represented by another step. So, for example, we may count
a simple assignment statement of the form a = 2 as one step and also count a
more complex statement such as a = 2*b+3=^c/d~e+f/g/a/b/c as one step. The
only requirement is that the time required to execute each statement that is
counted as one step be independent of the instance characteristics(instance
characteristics are input , output etc..)

➢ Determination of total steps required to complete the program

Using step count table

i. To construct a step count table we first determine the step count for each
statement. We call this the steps/execution, or s/e for short.
ii. Next we figure out the number of times that each statement is executed. We
call this the frequency. The frequency of a nonexecutable statement is zero.
iii. Multiplying s/e by the frequency, gives us the total steps for each statement.
Module I CS201 – Data Structures(KTU)

iv. Summing these totals, gives us the step count for the entire function

➢ Rules
o Comments and Declaration-step count=0
o Return and Assignment- step count=1
o Ignore constant multiplier
o Nested loops: The total running time of a statement inside a group of nested loop
is the running time of statement multiplied by the product of the size of all the
loops
for (i=0;i<n;i++)
for (j=0;j<n;j++)
k++
TC→ O(n2 )
o Consecutive statements: Maximum is one that counts
Eg: for (i=0;i<n;i++) → O(n)
a[i]=0;
for (i=0;i<n;i++) →O(n2 )
for (j=0;j<n;j++)
a[i]+= a[j]+i+j

➢ Examples

Eg [Link] the time and space complexity of the algorithm to find sum of elements in an array

Time Complexity = 2n + 3

Space Complexity = Space for parameters and Space for local

variablesA[]→n n→1 s→1 i→1
Space complexity = n + 3
Module I CS201 – Data Structures(KTU)

Eg2: Find the time and space complexity of matrix addition algorithm

Step/Execution Frequency Count Total Frequency Count

Algorithm mAdd(A,B,C,m,n) 0 0 0
{ 0 0 0
for i=0 to m-1 do 1 m+1 m+1
for j=0 to n-1 do 1 m(n+1) mn+m
C[i,j] := A[i,j] + B[i,j]; 1 mn mn
} 0 0 0
2mn + 2m +1
Time Complexity = 2mn + 2m + 1

Space Complexity = Space for parameters and Space for local variables
m→1 n→1 a[]→mn b[]→mn c[]→mn i→1 j→1
Space complexity = 3mn + 4

• Eg3: Find the time and space complexity of recursive sum algorithm

Space Complexity = Space for Stack

= Space for parameters + Space for local variables + Space for return
addressFor each recursive call the amount of stack required is 3
Space for parameters: list→1
n
→1 Space for local variables: No
local variablesSpace for return
address: 1
Total number of recursive call = n+1
Space complexity = 3(n+1)
Module I CS201 – Data Structures(KTU)

• Eg 4: Find the time and space complexity of matrix multiplication algorithm

Time complexity

Total Steps is 2N3+3N2+2N +1

Space complexity :

Space Complexity = Space for parameters and Space for local

variables
a[][]→N2
b[][]→N2
c[][]→N2
N→1
i→1
j→1
k→1
Space complexity = 3N2+ 4
Module I CS201 – Data Structures(KTU)

Eg5:Find the time complexity of

for (i=1;i<=n;i=i*2)
x=x+1;

in these cases, no of times the for statement executed can be computed as;

We know that at First iteration i=1

Second iteration i=2
Third iteration i=4
Fourth iteration i=8
Fifth iteration i=16

Therefore kth iteration i=2k-1

The loop body executes as long as i<=n

2k-1<=n
Taking log on both sides,
Log2 (2k-1)<=log2 (n)
(k-1) Log2 (2)<=log2 (n)
(k-1)<= log2 (n)
k<= log2 (n)+1

ie, the no of iterations the loop body will execute is Log2 (n)+1. And the for statement will execute one
more time(in that time, condition will became false and loop terminates)

Total step count is 2 log2 (n)+3

❖ Same logic can be used to find the time complexity of following algorithm

Q)Find the time complexity of

for(i=n;i>0;i=i/2)
x=x+1;
Module I CS201 – Data Structures(KTU)

BEST CASE, WORST CASE AND AVERAGE CASE COMPLEXITY (Explain with example:5 marks)

• In certain case we cannot find the exact value of frequency count. In this case we have 3 types
offrequency counts
o Best Case : It is the minimum number of steps that can be executed for a given parameter
o Worst Case: It is the maximum number of steps that can be executed for a given parameter
o Average Case: It is the average number of steps that can be executed for a given parameter
• Eg: Linear Search
o Best Case: Search data will be in the first location of the array.
o Worst Case: Search data does not exist in the array
o Average Case: Search data is in the middle of the array.

Best Case Worst Case Average Case

S/E FC TFC S/E FC TFC S/E FC TFC
Algorithm Search(a,n,x) 0 0 0 0 0 0 0 0 0
{ 0 0 0 0 0 0 0 0 0
for i:=1 to n do 1 1 1 1 n+1 n+1 1 n/2 n/2
if a[i] ==x then 1 1 1 1 n n 1 n/2 n/2
return i; 1 1 1 1 0 0 1 1 1
return -1; 1 0 0 1 1 1 1 0 0
} 0 0 0 0 0 0 0 0 0
3 2n + 2 n+1
Best Case Complexity = 3
Worst Case Complexity = 2n + 2
Average Case Complexity= n+1
Module I CS201 – Data Structures(KTU)

ASYMPTOTIC NOTATIONS (9 MARKS/4 MARKS)

• It is the mathematical notations to represent frequency count.

• 5 types of asymptotic notations

1. Big “Oh” (O)

• The function f(n) = O(g(n)) if there exists 2 positive constants c and n0 such that
0 ≤ f(n) ≤ c g(n) for all n ≥ n0
f(n)=computing time of some algorithm
g(n)=general function
▪ It is the measure of longest amount of time taken by an algorithm (Worst case).
▪ It is asymptotically tight upper bound

Eg:f(n)= 2n2 + n + 3

g(n)= n2
c=3

n f(n) c.g(n) 2n2 + n + 3≤ cn2

1 2x1+1+3=6 3x1=3 6≤3
2 2x4+2+3=13 3x4=12 13≤12
3 2x9+3+3=24 3x9=27 24≤27
f(n) ≤ c g(n) will true only at n value become [Link] n0 =3
TC=O(n2 ) when c=3 and n0 =3

2. Omega (Ω)
▪ The function f(n) = Ω (g(n)) if there exists 2 positive constant c and n0 such that
f(n) ≥ c g(n) ≥ 0 for all n ≥ n0
▪ It is the measure of smallest amount of time taken by an algorithm (Best case).
▪ It is asymptotically tight lower bound

Eg:f(n)= 2n2 + n + 3

g(n)= n2
Module I CS201 – Data Structures(KTU)
c=2
•

n f(n) c.g(n) 2n2 + n + 3≥ cn2

1 2x1+1+3=6 2x1=2 6≥2
• f(n) ≤ c g(n) will true only at n value become [Link] n0 =1
•
TC= Ω (n2 ) when c=2 and n0 =1

3. Theta (Ɵ)
▪ The function f(n) = Ɵ (g(n)) if there exists 3 positive constants c1, c2 and n0 such that
0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0
▪ It is the measure of average amount of time taken by an algorithm (Average case).
▪ Eg:f(n)= 2n2 + n + 3

g(n)= n2
c1=2
c2=3

n f(n) c1 g(n) c2.g(n) c1n2≤ 2n2 + n + 3

≤ c2n2
1 2x1+1+3=6 2x1=2 3x1=3 2≤6≤3
2 2x4+2+3=13 2x4=8 3x4=12 8≤13≤12
3 2x9+3+3=24 2x9=18 3x9=27 18≤24≤27

f(n) ≤ c g(n) will true only at n value become [Link] n0 =3

TC= Ɵ (n2 )
When c1=2 ,c2=3 and n0=3
Module I CS201 – Data Structures(KTU)

4. Little Oh (o)
▪ The function f(n) = o(g(n)) if for any positive constant c>0, there exists a constant n0>0 such
that 0 ≤ f(n) < c g(n) for all n ≥ n0
▪ It is asymptotically loose upper bound

Where g(n)!=0
g(n) becomes arbitrarily large relative to f(n) as n approaches infinity
5. Little Omega (ω)
▪ The function f(n) = ω(g(n)) if for any positive constant c>0, there exists a constant n0>0 such
that f(n) > c g(n) ≥ 0 for all n ≥ n0
▪ It is asymptotically loose lower bound

Where f(n)!=0
f(n) becomes arbitrarily large relative to g(n) as n approaches infinity

COMPARISON OF DIFFERENT TIME COMPLEXITIES

O(1) < O(log n) < O(n) < O(n log n) < O(nk) < O(2n) < O(n!)
Module I CS201 – Data Structures(KTU)

• Time Complexity Calculation: Examples

1. Find the time complexity of Binary Search

Algorithm BinarySearch(A, low, high, search_data)
{
flag=0
while low<=high do
{
mid = (low + high)/2
if A[mid]= search_data then
{
flag = 1
break
}
else if A[mid] > search_data then
high=mid-1
else
low=mid+1
}

if flag=0 then
Print “Search data not found”
else
Print “Search_data found at index “ mid
}

Time complexity of binary search is O(log n).Justify the answer(3 marks)

o Best Case Time Complexity of Binary Search
▪ The search data is at the middle index.
▪ So total number of iterations required is 1
▪ Therefore, Time complexity = O(1)

o Worst Case Time Complexity of Binary Search

▪ Assume that length of the array is n
▪ At each iteration, the array is divided by half.
▪ At Iteration 1, Length of array = n
▪ At Iteration 2, Length of array = n⁄2
▪ At Iteration 3, Length of array = (n⁄2)⁄2 = n⁄22
▪ At Iteration k, Length of array = n⁄2k-1
▪ After k divisions, the length of array becomes 1
n⁄2k-1 = 1
n = 2k-1
▪ Applying log function on both sides:
log2 (n) = log2 (2k-1)
log2 (n) = (k-1) log2 (2)
k = log2 (n) + 1
▪ Hence, the time complexity = O( log2 (n) )

o Average case Time Complexity of Binary Search

▪ Total number of iterations required = k/2 = (log2 (n)+1)/2
▪ Hence, the time complexity = O( log2 (n) )
Module I CS201 – Data Structures(KTU)
2. What is the time complexity of the following code
for(i=0; i<n; i++)
s=s+i;
Answer:
o The for loop will execute n+1 times. It is the most frequently executing statement.
o So the time complexity = n+1 = O(n)

3. What is the time complexity of the following code

for(i=0; i<n*n; i++)
s=s+i;
Answer:
o The for loop will execute n2+1 times. It is the most frequently executing statement.
o So the time complexity = n2+1 = O(n2)

4. What is the time complexity of the following code

i=1
while(i<=n)
{
s=s+i;
i=i*2;
}
Answer:
o The while loop will execute log n times.
o So the time complexity = log n = O(log n)

5. What is the time complexity of the following code

s=0
for(i=0; i<m; i++)
for(j=0; j<n;j++)
s=s+i*j;
Answer:
o The outer for loop will successfully execute m times
o For each successful case of outer for loop, the inner loop will successfully execute n times
o So the time complexity = m n = O(mn)

6. Calculate the frequency count of the statement x=x+1

for(i=1; i<=n; i++)
for(j=1; j<=n; j=j*2)
x=x+1;
Answer:
o The outer for loop will successfully execute n times
o For each successful case of outer for loop, the inner loop will successfully execute log n times
o So the frequency count of x=x+1 statement is n log n

7. Calculate the frequency count of the statement j=j*2

i=1;
while(i<=n)
{ j=1
while(j<=n)
{ j=j*2;
}
i=i+1;
}
Module I CS201 – Data Structures(KTU)
Answer:
o The outer while loop will successfully execute n times
o For each successful case of outer while loop, the inner loop will successfully execute log n times
o So the frequency count of j=j*2 statement is n log n = O(n log n)

8. What is the time complexity of the following code

s=0
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
s=s+i*j;
Answer:
o When i=1, the inner loop will execute 1 time
o When i=2, the inner loop will execute 2 time
o When i=n, the inner loop will execute n time
o So the innermost statement will execute 1+2+3+…..+ n = n(n+1)/2 times
o So the time complexity = n(n+1)/2 = O(n2)

9. What is the time complexity of the following code

s=0
for(i=1; i<=n; i++)
for(j=i; j<0; j++)
s=s+i*j;
Answer:
o The inner for loop will not execute at all. The frequency count of inner for loop is 0.
o The outer for loop will execute n times.
o So the time complexity = n = O(n)

10. Calculate the frequency count of the statement1

for(i=k; i<n; i=i*m)
Statement1;
Answer:
o The for loop will successfully execute ⌈logm (n/k)⌉ times
o So the frequency count of statement1 is ⌈logm (n/k)⌉ = O(⌈logm (n/k)⌉)

11. Calculate the frequency count of the statement1

for(i=k; i<=n; i=i*m)
Statement1;
Answer:
o The for loop will successfully execute ⌊ logm (n/k) + 1 ⌋ times
o So the frequency count of statement1 is ⌊ logm (n/k) + 1 ⌋ = O(⌊ logm (n/k) ⌋)

12. What is the time complexity of the following code

switch(key)
{
case 1: for(i=0;i<n;i++)
s=s+A[i]
break;
case 2: for(i=0;i<n;i++)
for(j=0;j<n;j++)
s=s+B[i][j]
break;
}

19 CS KTU Lectures
 Module I CS201 – Data Structures(KTU)
o
Answer:
o Case 1 complexity=O(n)
o Case 2 complexity=O(n2)
o The overall complexity = O(n2)

20 CS KTU Lectures

Protect pdf from copying with [Link]