---
title: 'Big-O Notation in 3 Minutes'
source: 'https://youtube.com/watch?v=x2CRZaN2xgM'
video_id: 'x2CRZaN2xgM'
date: 2026-09-03
duration_sec: 184
channel: 'ByteByteGo'
---

# Big-O Notation in 3 Minutes

> Source: [Big-O Notation in 3 Minutes](https://youtube.com/watch?v=x2CRZaN2xgM)

## Summary

This video provides a concise overview of Big-O notation, explaining how it measures algorithm efficiency by scaling with input size. It covers common complexities from fastest to slowest, and emphasizes that real-world performance is also influenced by hardware factors like caching and memory locality.

### Key Points

- **Definition of Big-O** [00:02] — Big-O measures how execution time scales with input size, crucial for optimizing code performance.
- **Constant Time (O(1))** [00:18] — Runtime remains constant regardless of input size; examples include array indexing, hash table operations.
- **Logarithmic Time (O(log n))** [00:32] — Runtime increases slowly with input size; binary search is a classic example, efficient for large datasets.
- **Linear Time (O(n))** [00:48] — Runtime grows directly proportional to input size; e.g., finding max in an unsorted array.
- **Linearithmic Time (O(n log n))** [01:00] — Efficient sorting algorithms like merge sort, quicksort, heapsort operate here; best possible for comparison-based sorting.
- **Quadratic Time (O(n^2))** [01:14] — Runtime grows proportional to square of input size; basic sorts like bubble sort, indicated by nested loops.
- **Cubic Time (O(n^3))** [01:26] — Runtime grows proportional to cube of input size; naive matrix multiplication is an example, often three nested loops.
- **Exponential Time (O(2^n))** [01:26] — Runtime doubles with each additional input element; seen in some recursive algorithms, impractical for large inputs.
- **Factorial Time (O(n!))** [01:42] — Runtime grows extremely fast; generating all permutations is an example, impractical for non-trivial input sizes.
- **Real-World Performance Factors** [01:56] — Big-O is just a start; caching, memory usage, and hardware specifics can affect actual performance. Maximizing cache hits can sometimes be more effective than reducing algorithmic complexity.
- **Example: Array Traversal** [02:08] — Row-wise traversal of a 2D array is often faster than column-wise due to sequential memory access and cache friendliness, despite both being O(n^2).
- **Example: Linked List vs Array** [02:22] — Both have linear traversal time, but arrays often outperform linked lists due to cache locality—elements are stored contiguously.
- **Conclusion and Advice** [02:35] — Use Big-O as a starting point, but profile your code, understand your hardware, and optimize for real-world conditions.

### Conclusion

Big-O notation is essential for understanding algorithmic efficiency, but real-world performance depends on hardware factors like caching and memory layout. Always profile and optimize for actual conditions.

## Transcript

ключ к пониманию эффективности алгоритмов. Big O измеряет, как время выполнения масштабируется в зависимости от размера входных данных, что имеет решающее значение для оптимизации производительности Cod. Давайте разберем распространенные обозначения от самого быстрого к самому медленному. Время выполнения за постоянное время
остается неизменным независимо от размера входных данных. Индексы массивов, операции с осью или хеш-таблицей — хорошие примеры. Время выполнения за логарифмическое время примеры. Время выполнения за логарифмическое время медленно увеличивается по мере роста входных данных; бинарный
поиск — классический пример. Эффективен для больших наборов данных; удвоение размера входных данных — всего лишь еще одна операция. Время выполнения за линейное время растет прямо пропорционально входным данным, например, поиск максимума в несортированном массиве. Если вам необходимо
обработать каждый элемент, то здесь начинается линейное арифметическое время. Именно здесь работают эффективные алгоритмы сортировки: сортировка слиянием, быстрая сортировка, пирамидальная сортировка — наилучший из
возможных вариантов для сортировки на основе сравнений. Время выполнения за квадратичное время растет пропорционально квадрату размера входных данных. Базовые алгоритмы сортировки, такие как пузырьковая сортировка, — обратите внимание на вложенные циклы, итерирующие по одним и тем же
данным. Время выполнения за кубическое время растет пропорционально кубу размера входных данных. Наивное умножение матриц — хороший пример. Три вложенных цикла часто указывают на кубическое время.
экспоненциальное время, удваивающееся с каждым дополнительным входным элементом. Вы увидите это в некоторых рекурсивных алгоритмах. Обработка небольших входных данных может занять много времени. Факториальное время, удваивающееся с размером входных данных, чрезвычайно быстро растет. Генерация всех
перестановок помещается здесь. Непрактично для нетривиальных размеров входных данных. Теперь вот нетривиальных размеров входных данных. Теперь вот важная часть: BigO — это только начало. Производительность в реальных условиях может отличаться из-за таких факторов, как кэширование, использование памяти и
особенности оборудования. В современных процессорах максимизация попаданий в кэш иногда может быть более эффективной, чем снижение сложности алгоритма. Два примера: первый —
сложности алгоритма. Два примера: первый — обход массива. Рассмотрим двумерный массив. Обход по строкам часто быстрее, чем по столбцам, хотя оба варианта имеют квадратичную временную сложность. Построчная ось максимизирует последовательный доступ к памяти и
последовательный доступ к памяти и дружественна к кэшу. Далее — связанный список против массива. Оба имеют линейную временную сложность для обхода, но массивы часто превосходят связанные списки из-за локальности кэша. Элементы массива расположены последовательно в памяти, в то время как элементы
связанного списка могут быть разбросаны. Итак, какой ваш вывод? Используйте PiO в качестве Профилируйте свой код, понимайте свое оборудование и оптимизируйте его для реальных условий, если хотите.
Возможно, вас также заинтересует новостная рассылка по системному проектированию, которая охватывает темы и тенденции в проектировании крупномасштабных систем. Ей доверяют 1 миллион читателей. Подпишитесь на этот million readers subscribe that blog blog. byby go.com