import random
from matplotlib import pyplot as plt
from matplotlib.ticker import ScalarFormatter

def recursive_find_smallest(A):
    if len(A) < 2:
        return A

    head = [A[0]] # A list with a single element
    tail = A[1:]
    
    smallest_in_tail = recursive_find_smallest(tail)

    if smallest_in_tail < head:
        return smallest_in_tail

    return head

def recursive_find_smallest_dc(A, low=0, high=None):
    # Initialize the high pointer on the very first call
    if high is None:
        high = len(A) - 1
        
    # Base case: If the section only has one element, it is the minimum
    if low == high:
        return A[low]
        
    # Divide: Find the midpoint of the current section
    mid = (low + high) // 2
    
    # Conquer: Recursively find the minimum of both halves
    min_left = recursive_find_smallest_dc(A, low, mid)
    min_right = recursive_find_smallest_dc(A, mid + 1, high)
    
    # Combine: Return the smaller of the two minimums
    if min_left < min_right:
        return min_left
    else:
        return min_right

list_sizes = [10, 100, 1000, 10000, 100000, 1000000, 10000000]
for n in list_sizes:
    A = random.sample(range(1, n * 5), n)
    %timeit recursive_find_smallest_dc(A)

864 ns ± 12.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
10.9 μs ± 1.28 μs per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
148 μs ± 2.17 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
The slowest run took 9.08 times longer than the fastest. This could mean that an intermediate result is being cached.
3.74 ms ± 3.5 ms per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
33.3 ms ± 18.6 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)
The slowest run took 4.76 times longer than the fastest. This could mean that an intermediate result is being cached.
259 ms ± 179 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
The slowest run took 4.29 times longer than the fastest. This could mean that an intermediate result is being cached.
5.03 s ± 3.02 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

# runtimes = [0.000908, 0.0231, 1.19, 1.55, 21.6, 294, 4930]
runtimes = [0.000864, 0.0109, 0.148, 3.74, 33.3, 259, 5030]

plt.plot(list_sizes, runtimes, marker='o') # Added marker to see points

plt.xscale('log')
plt.yscale('log')

# Create the formatter
formatter = ScalarFormatter()
formatter.set_scientific(False)

# Apply to BOTH axes manually
ax = plt.gca()
ax.xaxis.set_major_formatter(formatter)
ax.yaxis.set_major_formatter(formatter)

plt.title("Runtime vs List Size")
plt.xlabel("List Size")
plt.ylabel("Runtime (ms)")

# plt.ticklabel_format(style='plain', axis='both')  <-- REMOVE THIS LINE

plt.grid(True, which="both", ls="-", alpha=0.5) # Optional: helps see log scale
plt.show()

def minimum_from_exercise_6(A):
    v = A[0]                 
    for j in range(1, len(A)):   
        if A[j] < v:
            v = A[j]
    return v

%timeit minimum_from_exercise_6(A)

1.89 s ± 17.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)