Время выполнения операций, оценка...? С++

O (1) - означает, что время выполнения этих операций не зависит от размера элемента. Например, время получения 100-го элемента массива не будет отличаться для массива в 1000 элементов и для массива в 2000 элементов.
O (n) - означает линейную зависимость, например, для если для массива в 1000 элементов наша функция выполнится за t микросекунд, то для массива в 2000 элементов она выполнится приблизительно за 2t микросекунд.
O (n * log(n)) - значит, если мы увеличим наш входной массив в 2 раза, то времени будет затрачено в целом в 2 * log(2) раз больше.
O (n^2) - это квадратичная зависимость, увеличив входной массив вдвое, нам придётся примерно в 4 раза дольше ждать окончания работы нашей функции.
Большая О - означает худший случай, тета - средний случай, большая омега - лучший случай.
Программисты по своей природе пессимисты (программа должна предусматривать самые худшие варианты своего использования) - потому обычно для оценки применяется О (худший случай). Иногда желательно оценивать средний случай, если у двух алгоритмов худший случай примерно одинаков, а средний сильно отличается, либо если худший случай будет подаваться на вход крайне редко и им можно принебречь или отдельно определить и обработать другим алгоритмом.

Все эти операции выполняются за O(1).

Объявление переменных вообще не выполняется в ходе работы программы. Это просто информация для компилятора - такая-то ячейка будет обзываться так-то.
И что такое n? Компьютер, как известно, выполняет действия над последовательностями битов в основном параллельно.

добавление простой переменной (инициализация) на стак очень быстро происходит в районе наносекунд

Операции могут быть функцией какой угодно за счет оверлоадинга, но если брать обычные арифметические действия, то чисто технически умножение и деление дольше (все действия в районе наносекунд)

если брать сложность, а не время выполнения, то сильно зависит от используемого алгоритма и архитектуры
en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations
en.wikipedia.org/wiki/Multiplication_algorithm
en.wikipedia.org/wiki/Division_algorithm

Ну для начала, это сильно зависит от платформы и архитектуры ЦП.
1) Операция сравнения. На всех процессорах и контроллерах 1 такт
2) Операция присваивания. На больших системах с x86, ARM, MIPS, SH4, SH5 - есть кэш процессора. Если переменная уже в кэше, то 1 такт, если в ОЗУ, то до 200 тактов. На контроллерах 4-10 тактов.
3) Операция умножения. Тут сложнее. Во первых целые числа: На x86 порядка 70 тактов. На ЦП, где есть такая команда, порядок тот же. А на ЦП и контроллерах, где ее нет, все зависит от компилятора, но обычно не больше 200 тактов. Теперь с плавающей точкой. На ЦП с сопроцессором 5 тактов, включая загрузку и выгрузку данных из сопроцессора. Без него, так же зависит от компилятора и реализации, оценок не скажу.
4) Деления. Аналогично по стоимости умножению. Единственное, с плавающей точкой в режиме эмуляции оно выполняется раза в 1.5 дольше.
5) Сложения. 1 такт у всех
6) Вычитания. Это то же сложение с инверсией. 1-2 такта
Такие операции в теории алгоритмов принимают как О (1), т. е. константное время выполнения.

"время выполнения объявления переменной" происходит на этапе компиляции.