South East University
CSE 246(Algorithms)
Lab-4 Manual
(Analyzing and Optimizing Algorithm Performance)
Course instructor
Dr. Md. Tauhid Bin Iqbal
Assistant Professor
Department of Computer Science & Engineering
Basic Idea of Time Complexity and Space Complexity
Time Complexity and Space Complexity are two crucial aspects of analyzing
algorithms, which help determine their efficiency in terms of time and memory usage.
Time Complexity:
Time complexity measures how the runtime of an algorithm increases as the input
size grows. Algorithms with O(n) scale linearly, while those with O(n²) grow
quadratically, making them slower for large inputs. Optimizing time complexity is
essential to improve performance and reduce execution time, especially for large
datasets.
Fig: Time Complexity compare
Space Complexity:
Space complexity refers to the amount of memory an algorithm uses relative to the
input size. High space complexity can cause memory issues, especially in resource-
limited environments. Optimizing space ensures efficient memory usage and prevents
overflow, particularly when dealing with large datasets.
Fig: Time Complexity and Space Complexity compare
1st problem:Sum of All Elements in an Array
Explanation:
#include <iostream>
using namespace std; #include <iostream>
using namespace std;
int main() {
int original[] = {1, 2, 3, 4, 5}; int sumArray(int arr[], int n) {
int n = 5; int total = 0;
for(int i = 0; i < n; i++) {
int copy[100]; total += arr[i];
for(int i = 0; i < n; i++) { }
copy[i] = original[i]; return total;
} }
int partialSum[100]; int main() {
for(int i = 0; i < n; i++) { int arr[] = {1, 2, 3, 4, 5};
int sum = 0; int n = 5;
for(int j = 0; j <= i; j++) {
sum += copy[j]; cout << "Optimized Sum = " <<
} sumArray(arr, n) << endl;
partialSum[i] = sum;
} return 0;
}
// Step 3: Take the last element as the total
sum
int total = partialSum[n - 1];
cout << "Sum of array = " << total << endl;
return 0;}
Total Time Complexity: O(n²) and space O(n) Total Time Complexity: O(n) and
space O(1)
Lab Tasks:
In this task, you are given six pieces of code. The first step is to detect the time and
space complexity of each given code. Then, you need to write an optimized version of
each code with improved time and space complexity. After optimizing, you should
also determine the time and space complexity of the optimized code.
Original Code: You are given code that solves a problem inefficiently, such as using
nested loops or unnecessary extra memory.
Step 1: Analyze Complexity: Evaluate the time and space complexity of the original
solution. Look for nested loops, recursive calls, or excessive use of space like lists or
hash maps.
Step 2: Optimize: Redesign the code to reduce the time complexity by minimizing
the number of operations (e.g., using better algorithms or data structures). If possible,
reduce space complexity by using in-place algorithms or minimizing extra data
storage.
Step 3: Provide Optimized Code and Its Complexity: Write the optimized code and
calculate its time and space complexity. Provide explanations about how the
optimization was achieved.
Submission instructions: After solving the problems need to give the original code
and it’s complexity and the in the next column the optimized code and that’s
complexities as table format as the first problem is solved and showed.
Problem 2: search a element in a array
#include <iostream>
using namespace std;
int main() {
int arr[] = {4, 8, 1, 7, 3};
int n = 5;
int x = 7;
bool found = false;
for(int i = 0; i < n; i++) {
int current = arr[i];
if(current == x) {
for(int j = i; j < n; j++) {
if(arr[j] == x) {
found = true;
break;
}
}
break;
}
}
if(found)
cout << "Element " << x << " is present in the array." << endl;
else
cout << "Element " << x << " is NOT present in the array." << endl;
return 0;
}
Problem 3: Reverse an Array
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = 5;
int copy[100];
for(int i = 0; i < n; i++) {
copy[i] = arr[i];
}
int reversed[100];
for(int i = 0; i < n; i++) {
reversed[i] = copy[n - 1 - i];
}
cout << "Reversed Array: ";
for(int i = 0; i < n; i++) {
cout << reversed[i] << " ";
}
cout << endl;
return 0;
}
Problem 4: Finding Maximum in an Array
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int maxArr[100];
for(int i = 0; i < n; i++) {
maxArr[i] = arr[i];
}
int maxVal = maxArr[0];
for(int i = 1; i < n; i++) {
if(maxArr[i] > maxVal) {
maxVal = maxArr[i];
}
}
cout << "Maximum Element: " << maxVal << endl;
return 0;
}
Problem 5: Remove Duplicate Elements from an Array
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 2, 4, 5, 5};
int n = 7;
int copy[100];
for(int i = 0; i < n; i++) {
copy[i] = arr[i];
}
int unique[100];
int uniqueCount = 0;
for(int i = 0; i < n; i++) {
bool found = false;
for(int j = 0; j < uniqueCount; j++) {
if(copy[i] == unique[j]) {
found = true;
break;
}
}
if(!found) {
unique[uniqueCount++] = copy[i];
}
}
cout << "Array with unique elements: ";
for(int i = 0; i < uniqueCount; i++) {
cout << unique[i] << " ";
}
cout << endl;
return 0;
}
Problem 6: Check if a Sub array with Given Sum Exists
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {1, 2, 3, 7, 5};
int n = arr.size();
int targetSum = 12;
bool found = false;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += arr[k];
}
if (sum == targetSum) {
found = true;
break;
}
}
if (found) break;
}
if (found) {
cout << "Subarray with given sum exists." << endl;
} else {
cout << "No subarray with given sum exists." << endl;
}
return 0;
}
Problem 7: Find the First Repeated Element in an Array
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {1, 2, 3, 4, 5, 3, 6, 7};
int n = arr.size();
int repeatedElement = -1;
bool found = false;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) {
repeatedElement = arr[i];
found = true;
break;
}
}
if (found) break;
}
if (repeatedElement != -1) {
cout << "First repeated element: " << repeatedElement << endl;
} else {
cout << "No repeated elements found." << endl;
}
return 0;
}
Problem 8: Count every even numbers in an array
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 5};
int n = 2;
int totalEven = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++) {
if (arr[k] % 2 == 0) {
totalEven++;
}
}
}
}
cout << "Total even numbers in all subarrays: " << totalEven << endl;
return 0;
}
