Polynomial Curve

merge_sort.py

def merge_two_sorted_arrs(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge_two_sorted_arrs(left, right)

# Test the function
arr = [5,2,4,7,1,3,2,6]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)

Q2.py

import time
import numpy as np
import matplotlib.pyplot as plt

def f(n):
    x = 1
    for i in range(1, n+1):
        for j in range(1, n+1):
            x += 1
    return x

# Measure execution time for various values of n
ns = np.arange(1, 1000)  # Values of n from 1 to 999
times = []

for n in ns:
    start_time = time.time()
    f(n)
    end_time = time.time()
    times.append(end_time - start_time)

# Fit a quadratic polynomial T(n) ≈ a n^2 + b n + c
z = np.polyfit(ns, times, 2)
a, b, c = z  # Extract coefficients

# Define upper and lower bound constants
c1 = 0.7 * a  # Lower bound coefficient
c2 = 1.2 * a  # Upper bound coefficient

# Define the bounds
upper_bound = lambda n: c2 * n**2
lower_bound = lambda n: c1 * n**2

# Plot time vs n
plt.figure(figsize=(10, 6))
plt.plot(ns, times, 'o-', markersize=2, label="Measured Time", alpha=0.6)
plt.plot(ns, a * ns**2 + b * ns + c, "r--", label=f"Fitted: {a:.2e}n² + {b:.2e}n + {c:.2e}")
plt.plot(ns, upper_bound(ns), "g-", label=f"Upper Bound: {c2:.2e}n²")
plt.plot(ns, lower_bound(ns), "b-", label=f"Lower Bound: {c1:.2e}n²")

plt.xlabel('n')
plt.ylabel('Time (s)')
plt.title('Execution Time vs n with Upper and Lower Bounds')
plt.legend()
plt.grid(True)
plt.show()

# Print the polynomial coefficients and bounds
print(f"Fitted Quadratic Coefficient: a = {a:.5e}")
print(f"Upper Bound Coefficient: c2 = {c2:.5e}")
print(f"Lower Bound Coefficient: c1 = {c1:.5e}")

Q4.py

import time
import numpy as np
import matplotlib.pyplot as plt

def f_original(n):
    x = 1
    for i in range(1, n+1):
        for j in range(1, n+1):
            x += 1
    return x

def f_modified(n):
    x = 1
    y = 1
    for i in range(1, n+1):
        for j in range(1, n+1):
            x += 1
            y = i + j
    return x

# Measure execution time for various values of n
ns = np.arange(1, 2000, 10)  # Values of n from 1 to 500 with step 10 for efficiency
times_original = []
times_modified = []

for n in ns:
    # Time original function
    start_time = time.time()
    f_original(n)
    end_time = time.time()
    times_original.append(end_time - start_time)

    # Time modified function
    start_time = time.time()
    f_modified(n)
    end_time = time.time()
    times_modified.append(end_time - start_time)

# Plot execution time for both functions
plt.figure(figsize=(10, 6))
plt.plot(ns, times_original, 'bo-', markersize=3, label="Original Function")
plt.plot(ns, times_modified, 'ro-', markersize=3, label="Modified Function")
plt.xlabel('n')
plt.ylabel('Time (s)')
plt.title('Execution Time Comparison: Original vs Modified Function')
plt.legend()
plt.grid(True)
plt.show()