CODE REFACTORING EXAMPLE_OPTIMIZATION
1.
let's consider a simple C program that calculates the factorial of a given number. Initially,
we'll start with a straightforward implementation and then refactor it to improve its time
complexity.
Before Refactoring:
#include <stdio.h>
// Function to calculate factorial
int factorial(int n) {
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
int main() {
int num;
printf("Enter a number: ");
scanf("%d", &num);
printf("Factorial of %d is %d\n", num, factorial(num));
return 0;
}
In the initial implementation, the time complexity of calculating the factorial using recursion
is O(n), where n is the input number.
After Refactoring:
We can refactor the program to calculate factorial iteratively, which would improve its time
complexity.
#include <stdio.h>
// Function to calculate factorial
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
int main() {
int num;
printf("Enter a number: ");
scanf("%d", &num);
printf("Factorial of %d is %d\n", num, factorial(num));
return 0;
}
In the refactored version, we've eliminated the recursion and used a simple loop instead. This
results in a time complexity of O(n) as well, but it's generally more efficient due to avoiding
the overhead of function calls and stack usage associated with recursion.
2.
let's consider another example where we calculate the nth Fibonacci number.
Before Refactoring:
#include <stdio.h>
// Function to calculate nth Fibonacci number using recursion
int fibonacci(int n) {
if (n <= 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int num;
printf("Enter a number: ");
scanf("%d", &num);
printf("Fibonacci number at position %d is %d\n", num, fibonacci(num));
return 0;
}
In the initial implementation, the time complexity of calculating the nth Fibonacci number
using recursion is O(2^n), which is highly inefficient as it recalculates the same subproblems
multiple times.
After Refactoring:
We can refactor the program to use dynamic programming, specifically memoization, to
improve its time complexity.
#include <stdio.h>
// Function to calculate nth Fibonacci number using dynamic programming (memoization)
int fibonacci(int n) {
int fib[n+2];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[n];
}
int main() {
int num;
printf("Enter a number: ");
scanf("%d", &num);
printf("Fibonacci number at position %d is %d\n", num, fibonacci(num));
return 0;
}
In the refactored version, we've used an array to store previously calculated Fibonacci
numbers, thus avoiding redundant calculations. This results in a time complexity of O(n),
significantly improving the performance compared to the recursive version.
3.
Let's consider an example where we want to find the maximum element in an array.
Before Refactoring:
#include <stdio.h>
// Function to find the maximum element in an array
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
int main() {
int arr[] = {3, 7, 2, 8, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("The maximum element in the array is: %d\n", findMax(arr, n));
return 0;
}
In the initial implementation, the time complexity of finding the maximum element in an
array is O(n), where n is the number of elements in the array.
After Refactoring:
We can refactor the program to reduce its time complexity by sorting the array first and then
picking the last element, which is guaranteed to be the maximum.
#include <stdio.h>
#include <stdlib.h>
// Function to find the maximum element in an array
int findMax(int arr[], int n) {
// Sort the array in ascending order
qsort(arr, n, sizeof(int), compare);
// Return the last element which is the maximum
return arr[n - 1];
}
// Comparison function for qsort
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int main() {
int arr[] = {3, 7, 2, 8, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("The maximum element in the array is: %d\n", findMax(arr, n));
return 0;
}
In the refactored version, we've sorted the array using qsort function which generally has a
time complexity of O(nlog(n)). Then, we return the last element of the sorted array, which is
the maximum. The overall time complexity becomes O(nlog(n)), which is better than the
previous implementation in cases where n is large.
4.
Let's consider an example where we want to find if a given number is prime or not.
Before Refactoring:
#include <stdio.h>
// Function to check if a number is prime
int isPrime(int n) {
if (n <= 1)
return 0; // Not prime
for (int i = 2; i < n; i++) {
if (n % i == 0)
return 0; // Not prime
}
return 1; // Prime
}
int main() {
int num;
printf("Enter a number: ");
scanf("%d", &num);
if (isPrime(num))
printf("%d is a prime number.\n", num);
else
printf("%d is not a prime number.\n", num);
return 0;
}
In the initial implementation, the time complexity of checking if a number is prime is O(n),
where n is the input number.
After Refactoring:
We can refactor the program to improve its time complexity by reducing the number of
iterations.
#include <stdio.h>
#include <math.h>
// Function to check if a number is prime
int isPrime(int n) {
if (n <= 1)
return 0; // Not prime
if (n <= 3)
return 1; // 2 and 3 are prime
// Check if n is divisible by 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return 0; // Not prime
// Check divisibility by numbers of the form 6k ± 1
for (int i = 5; i <= sqrt(n); i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return 0; // Not prime
}
return 1; // Prime
}
int main() {
int num;
printf("Enter a number: ");
scanf("%d", &num);
if (isPrime(num))
printf("%d is a prime number.\n", num);
else
printf("%d is not a prime number.\n", num);
return 0;
}
In the refactored version, we've reduced the number of iterations by checking divisibility only
up to the square root of the number. Additionally, we've optimized the loop to check
divisibility only for numbers of the form 6k ± 1. This significantly reduces the number of
iterations required to determine primality. The overall time complexity becomes O(sqrt(n)),
which is much better than the previous implementation, especially for large values of n.
5.
Let's consider an example where we want to compute the sum of elements in an array.
Before Refactoring:
#include <stdio.h>
// Function to compute the sum of elements in an array
int arraySum(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
return sum;
}
int main() {
int arr[] = {3, 7, 2, 8, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("The sum of elements in the array is: %d\n", arraySum(arr, n));
return 0;
}
In the initial implementation, the time complexity of computing the sum of elements in an
array is O(n), where n is the number of elements in the array.
After Refactoring:
We can refactor the program to improve its time complexity by dividing the array and
summing in parallel, effectively reducing the number of operations.
#include <stdio.h>
#include <omp.h>
// Function to compute the sum of elements in an array using parallelization
int arraySum(int arr[], int n) {
int sum = 0;
#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < n; i++) {
sum += arr[i];
}
return sum;
}
int main() {
int arr[] = {3, 7, 2, 8, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("The sum of elements in the array is: %d\n", arraySum(arr, n));
return 0;
}
In the refactored version, we've utilized OpenMP to parallelize the sum computation. The
#pragma omp parallel for directive distributes the loop iterations across available threads, and
reduction(+:sum) ensures that each thread maintains its local sum, which is then combined at
the end. This effectively reduces the time complexity of summing the array to O(log(n)),
where n is the number of elements in the array.
