Це тільки підтверджує, що відеоуроки - то фігня. Дві години вбили і ніц не зрозуміли.
O(n) означає, що кількість операцій час роботи програми залежить від кількості вхідних даних лінійно, на кшталт k+l*n, де k - час на фіксовані дії (ініціалізацію змінних і вивід результату, наприклад), а l - час на обробку одиниці вхідних даних. Наприклад, програма, що шукає максимум, має саме таку складність: деякі операції будуть виконані незалежно від того, скільки є вхідних даних і чи є вони взагалі, а деякі (ввід, порівняння і присвоювання) - стільки разів, скільки є вхідних значень. Так, деякі операції (присвоювання в результаті порівняння) будуть виконуватися не завжди, але для простоти беремо найгірший випадок і вважаємо, що вони будуть завжди; ну і, зрештою, якщо масив буде впорядкований по зростанню, то ввід, присвоювання і порівняння будуть виконуватися завжди (час, умовно, k+3*n), а якщо максимум буде першим, то ніколи (k+2*n). Обидва вирази лінійні, тобто складність завжди O(n).
А логарифмічна складність виникає, коли об'єм даних, що лишився, зменшується на кожному кроці в певну кількість разів. Наприклад бінарний пошук по впорядкованому масиву - беремо середину, якщо не вгадали - беремо середину того відрізку, що лишився і т.д. - має логарифмічну складність.
В чому сенс цього всього? В тому, що реальним алгоритмам треба обробляти дуже великі об'єми даних. Настільки великі, що число k взагалі непомітне (що таке п'ять хвилин прогріву, якщо алгоритм буде працювати два місяці?), а зменшення коефіціенту l удвічі - ніщо порівняно із заміною алгоритму на інший з логарифмічною складністю. Хоча, звісно, треба бути обережним, а то алгоритм Коперсміта-Винограда вийде - він, звісно, оптимальніший за інші, але тільки для матриць, яким на сучасних носіях знадобиться більше фізичного місця, ніж його займає Земля.

Так, але ви не використали свої вхідні дані, тому не знаю, чи є тут сенс говорити про якусь складність.

Що дати, вибачте?

Та ж сама O(n). Можете переконатись в цьому, підрахувавши кількість операцій і відкинувши доданки меншого порядку та коефіцієнти.

Це приклад якраз складності O(1) - якщо на вхід дати одне значення чи мільярд, то все одно буде виконано 15000 операцій. Головне тут - розрізняти реальні випадки O(1) від замаскованих, які працюють тільки коли n<15000.
Якщо вам реальний приклад - то пошук в хеш-таблиці має складність O(1).

Круто, буду сидіти і розбирати. Дякую, заки

P.S. Але питання ще будуть!

Ой вибачте, я незамітив, що log - змінна

O(1) ми маємо тоді, коли кількість операцій не залежить від величини вхідних даних. В цьому випадку якою б не була n, програма виконає однакову кількість операцій — просто порахує дві формули.

Рахувати кількість цифр в числах від 1 до n можна кількома способами. Найбільш наївний спосіб — це просто взяти і порахувати кількість цифр:

int count = 0;
for(int i = 1; i <= n; i++){
    int temp = i;
    while(temp > 0){
        count++;
        temp /= 10;
    }
}

Наївний спосіб має складність O(n*log(n))¹ — n раз виконуємо не більше ніж log(n) операцій.

Тут можна згадати про те, кількість цифр в числі n дорівнює log10(n) + 1. Замінивши внутрішній цикл цією формулою, отримаємо O(n):

int count = 0;
for(int i = 1; i <= n; i++){
    int temp = i;
    count += log10(n) + 1;
}

Наступна сходинка еволюції — помітити, що від 1 до 10 є 9*1 цифр, від 10 до 100 є 90*2 цифр, і т. д. Обчислимо їх всіх і складемо докупи. Отримуємо складність O(log(n)).

int res = 0;
while(i < n){
    res += (i - i/10)*log10(i);
    i *= 10;
}
res += (n - i/10)*log10(i)+log10(n)+1;

Ну і коли ми зможемо позбутись і цього циклу, обчислюючи дві формули для будь-якого числа, ми отримаємо алгоритм складністю O(1).

¹Насправді O(log(n!)). Але графік n*log(n) - log(n!) сильно схожий на лінію, тому я насмілюсь припустити, що log(n!) = n*log(n) - a*n, з подальшим відкиданням меншого доданка.

Логарифми відрізняються один від одного лише константним множником, тому про основу ніхто не говорить.

Прикладів хочете? Нате.

1. На вхід подається список з стрінгі́в, які представляють послідовно записані числа у довільній системі числення. Яку складність матиме алгоритм, що визначає цю систему числення?

2. Знайдіть складність алгоритму множення в стовпчик.

Може ще щось придумаю.

Додавання виконувати також за допомогою довгої арифметики, чи достатньо простою операцією +   ?