Department of Computer and Software Engineering- ITU
CE200L: Data Structures and Algorithms Lab
Course Instructor: Ms. Aqsa Khalid Dated:
Lab Engineer: Usama Riaz Semester: Fall 2024
Session: 2023-2027 Batch: BSCE2023
Lab 2. Performance Analysis of a Program in terms of Time &
Space Complexity
Name Roll number Obtained Marks/35
Abdullah Basit Awan BSCE23013
Checked on:
Signature:
Objective
The objective of this course is to provide the knowledge of basic data structures and their implementations.
Equipment and Component
Component Description Value Quantity
Computer Available in lab 1
Conduct of Lab
1. Students are required to perform this experiment individually.
2. In case the lab experiment is not understood, the students are advised to seek help from the
course instructor, lab engineers, assigned teaching assistants (TA) and lab attendants.
Theory and Background
Time Complexity is a type of computational complexity that describes the time required to execute an
algorithm. The time complexity of an algorithm is the amount of time it takes for each statement to complete.
As a result, it is highly dependent on the size of the processed data. How much time does mean:
How fast is your computer? Are we running other programs simultaneously? Which programming languages
you are using etc.
It is basically how the time taken to execute the program increases with the increase in input size. There are
three types of measurements such as: Best Case, Average Case, Worst Case. Rules for calculating complexity:
1. Find the fastest growing term (dominating term) & ignore low order terms.
2. Take out the coefficient (ignore constant).
Space Complexity of a program is the amount of memory it needs to run to completion.
Tasks
Task 1: Accept the assignment posted in Google Classroom and after accepting clone the repository to your
computer for this ensure you have logged into github app with your account.
Task 2: Solve the given problems written after task instructions, write code through IDE like CLion
Task 3: Ensure your code/solution is in the cloned folder.
Task 4: Commit and Push the changes through the Github App
Task A
Find the time and space complexities of the following expression & codes and express it in terms of big
O:
a) x = 15 – (35/7);
Statement Cost Repetition Total
x = 15 – (35/7); 1 1 1
Time Complexity: O(1)
Space Complexity: O(1)
b) x = 15 – (35/7);
cout<<x;
y = 5*9;
cout<<y;
Statement Cost Repetition Total
x = 15 – (35/7); 1 1 1
cout<<x; 1 1 1
y=5*9; 1 1 1
cout<<y; 1 1 1
Time Complexity: O(1)
Space Complexity: O(1)
c) for(i=1; i<n; i++)
cout<<i;
Statement Cost Repetition Total
i=1 1 n n
i<n 1 n-1 n-1
i++ 1 n n
cout<<i; 1 n-1 n-1
Time Complexity: O(n)
Space Complexity: O(1)
d) cout<<”Enter value of n”;
cin>>n;
for(i=1; i<=n; i++)
cout<<i;
Statement Cost Repetition Total
cout<<”Enter value 1 1 1
of n”;
cin>>n; 1 1 1
i=1 1 n n
i<=n 1 n n
i++ 1 n n
cout<<i; 1 n-1 n-1
Time Complexity: O(n)
Space Complexity: O(1*2)=O(1)
e) for(x=1; x<=n; x++)
for(y=1; y<=n; y++;)
cout<<x+y;
Statement Cost Repetition Total
x=1; 1 n n
x<=n; 1 n n
x++; 1 n+1 n+1
y=1; 1 n n
y<=n; 1 n n
y++; 1 n+1 n+1
cout<<x+y; 1 n^2 n^2
Time Complexity: O(n^2)
Space Complexity: O(3*1)=O(1)
f) x=5*9;
for(i=1; i<=n; i++)
cout<<i;
for(x=1; x<=n; x++)
for(y=1; y<=n; y++)
cout<<x*y;
Statement Cost Repetition Total
x=5*9; 1 1 1
i=1; 1 1 1
i<n; 1 n n
i++; 1 n-1 n+1
cout<<i; 1 n n
x=1; 1 1 1
x<=n; 1 n n
x++; 1 n+1 n+1
y=1; 1 n n
y<=n; 1 n n
y++; 1 n+1 n+1
cout<<x*y; 1 n^2 n^2
Time Complexity: O(n^2)
Space Complexity: O(4*1)=O(1)
Task B
For the following codes carry out the analytical analysis to evaluate time and space complexity and
express it in terms of Big O:
int sum, i; int sum,i,j;
sum=0; sum=0;
for(i=0;i<n;++i) for(i=1;i<n;i=i*2)
sum++; sum++;
int sum,i,j; int sum,i,j;
sum=0; sum=0;
for(i=1;i<=n;++i) for(i=0;i<n;++i)
{ {
for(j=0;j<i;++j) for(j=0;j<n;++j)
{ {
sum++; sum++;
} }
} }
int sum,i,j; int sum,i,j;
sum=0; sum=0;
for(i=1;i<=n;i=i*2) for(i=1;i<=n;i=i*2)
{ {
for(j=0;j<n;++j) for(j=0;j<i;j++)
{ {
sum++; sum++;
} }
} }
1)
Statement Cost Repetition Total
int sum, i, j; 1 1 1
sum=0; 1 1 1
i=0; 1 1 1
i<n; 1 n-1 n-1
++i; 1 n n
sum++; 1 n n
Time Complexity: O(n)
Space Complexity: O(3*1)=O(1)
2)
Statement Cost Repetition Total
int sum, i; 1 1 1
sum=0; 1 1 1
i=1; 1 1 1
i<i*2; 1 log(n)-1 log(n)-1
++i; 1 log(n) log(n)
sum++; 1 log(n) log(n)
Time Complexity: O(n)
Space Complexity: O(2*1)=O(1)
3)
Statement Cost Repetition Total
int sum, i, j; 1 1 1
sum=0; 1 1 1
i=1; 1 1 1
i<=n; 1 n n
++i; 1 n+1 n+1
j=0; 1 n n
j<i; 1 n^2 n^2
++j; 1 n^2-1 n^2-1
sum++ 1 n^2 n^2
Time Complexity: O(n^2)
Space Complexity: O(1*3)=O(1)
4)
Statement Cost Repetition Total
int sum, i, j; 1 1 1
sum=0; 1 1 1
i=1; 1 1 1
i<n; 1 n+1 n+1
++i; 1 n+1 n+1
j=0; 1 n n
j<n; 1 n^2 n^2
++j; 1 n^2+1 n^2+1
sum++ 1 n^2 n^2
Time Complexity: O(n^2)
Space Complexity: O(1*3)=O(1)
5)
Statement Cost Repetition Total
int sum, i, j; 1 1 1
sum=0; 1 1 1
i=1; 1 1 1
i<=n; 1 n n
i=i*2; 1 n n
j=0; 1 n n
j<n; 1 n^2 n^2
++j; 1 n^2-1 n^2-1
sum++ 1 n^2 n^2
Time Complexity: O(n^2)
Space Complexity: O(3*1)=O(1)
6)
Statement Cost Repetition Total
int sum, i, j; 1 1 1
sum=0; 1 1 1
i=1; 1 1 1
i<=n; 1 n n
i=i*2; 1 n n
j=0; 1 n n
j<i; 1 n^2 n^2
j++; 1 n^2+1 n^2+1
sum++ 1 n^2 n^2
Time Complexity: O(n^2)
Space Complexity: O(3*1)=O(1)
Assessment Rubric for Lab
Performance metric Able to complete the task Able to complete the Able to complete the
CLO Marks
over 80% (4-5) task 50-80% (2-3) task below 50% (0-1)
Executes without errors, Does not execute due
Executes without errors
user prompts are to syntax errors,
excellent user prompts,
understandable, runtime errors, user
good use of symbols,
1. Realization of minimum use of symbols prompts are
1 spacing in output.
experiment or spacing in output. misleading or non-
Through testing has been Some testing has been existent. No testing
completed. completed. has been completed.
Able to make changes Partially able to make Unable to make
2. Conducting
1 and answered all changes and few changes and answer
experiment
questions. incorrect answers. all questions.
Document submission Document submission Document
3. Computer use 2
timely. late. submission not done.
Distracts or
Actively engages and Cooperates with other
discourages other
cooperates with other group member(s) in a
4. Teamwork group members from
3 group member(s) in reasonable manner but
conducting the
effective manner. conduct can be improved. experiment
Code comments are Code comments are
5. Laboratory safety added and does help the added and does not help Code comments are
and disciplinary reader to understand the the reader to understand
3 not added.
rules code. the code.
Excellent use of white
Includes name, and Poor use of white
space, creatively
assignment, white space space (indentation,
organized work,
makes the program fairly blank lines) making
6. Data collection 3 excellent use of variables
easy to read. Title, code hard to read,
and constants, correct
organized work, good use disorganized and
identifiers for constants,
No line-wrap. of variables. messy.
Solution is efficient, easy A logical solution that is
A difficult and
7. Data analysis 4 to understand, and easy to follow but it is not
inefficient solution.
maintain. the most efficient.
Total (out of 35):
