Какова временная сложность выборки?

В моем тестировании выглядит линейным, если N > 30 000, где среднее время выборки для 10 выборок из 1:N составляет около 0,5 микросекунды на значение в диапазоне. При меньшем N, по-видимому, возникают накладные расходы, из-за которых время на выборку увеличивается.

sample_range = 10^seq(2, 7, 0.05)

take_sample <- function(n) {
    test <- microbenchmark::microbenchmark(
              sample(n, 10), times = 100, unit = "microseconds")
    avg = mean(test$time)
    data.frame(n, avg)
  }

# takes about 20 sec on my machine
sample_results <- lapply(sample_range, take_sample)

Затем, чтобы показать эти результаты:

library(tidyverse)
bind_rows(sample_results) |>
  mutate(microsec_per_range = avg / n) |>
  ggplot(aes(n, microsec_per_range)) +
  geom_point() +
  expand_limits(y = 0) +
  scale_x_log10(breaks = c(10^(2:7), 3*10^(2:7)),
                labels = scales::comma_format()) +
  scale_y_continuous(breaks = c(0, 0.3, 1, 3, 10, 30, 100),
                     trans = scales::pseudo_log_trans(sigma = 0.1))