Меня несколько смущают следующие алгоритмы. В частности, я не понимаю, почему первым является O (n), а вторым - O (n ^ 2). Возможно, моя единственная интуиция заключается в том, что внутренние и внешние циклы для первого алгоритма не «связаны». Во-вторых, я могу интуитивно видеть, что вторым алгоритмом является O (n ^ 2), но как нам найти некоторые константы c1, c2, чтобы доказать, что f (n) - это big-0 и little-0 из n ^ 2?

sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
    sum++;

sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        sum++;