Я несколько смущен следующими алгоритмами. В частности, я неЯ не понимаю, почему первым является 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++;