Exploring how algorithm speed changes as input grows.

We’ll compare:

• Bubble Sort — simple but slow
  
• Merge Sort — smarter divide-and-conquer

We’ll measure how run-time increases as input size grows.

• In computer science, we use statistics to measure algorithm efficiency.
• The complexity, or growth-rate, is described using Big-O notation:

\[ O(n^2) \quad \text{vs.} \quad O(n \log n) \]

set.seed(1)
n <- seq(100, 5000, by=500)
bubble <- 0.000002 * n^2 + rnorm(length(n), 0, 20)
merge  <- 0.00005 * n * log(n) + rnorm(length(n), 0, 20)
data <- data.frame(n, bubble, merge)
head(data)

##      n     bubble       merge
## 1  100 -12.509076  30.2586492
## 2  600   4.392866   7.9887726
## 3 1100 -14.292572 -12.0396430
## 4 1600  37.025616 -43.7037770
## 5 2100  15.410155  23.3018361
## 6 2600  -2.889368   0.1235525

data_long <- pivot_longer(data, c(bubble, merge), names_to="algo", values_to="time")

ggplot(data_long, aes(n, time, color=algo)) +
  geom_line(size=1) +
  labs(title="Runtime vs Input Size",
       x="Input Size (n)", y="Time (ms)", color="Algorithm") +
  theme_minimal()

ggplot(data_long, aes(log(n), log(time), color=algo)) +
  geom_point() +
  geom_smooth(method="lm", se=FALSE) +
  labs(title="Log-Log Plot: Detecting Growth Rate",
       x="log(n)", y="log(Time)") +
  theme_minimal()

plot_ly(data_long, x=~n, y=~algo, z=~time, color=~algo) |>
  add_markers() |>
  layout(scene = list(xaxis=list(title="n"),
                      yaxis=list(title="Algorithm"),
                      zaxis=list(title="Time (ms)")))

• Bubble Sort grows roughly like \(n^2\).
  
• Merge Sort grows like \(n \log n\).
  
• Plots and regression analysis are two ways statistics aid in the visualization of algorithm performance.