CODEWITHSUNDEEP
algorithmbig-otime-complexity
codeMonkey17
codeMonkey17

Reputation: 131

Running time complexity of double for-loops

I'm somewhat confused by the following algorithms. In particular, I don't understand why the first is O(n) and the second is O(n^2). My only intuition is perhaps that the inner and outer loops for the first algorithm aren't "linked." Secondly, I can intuitively see that the second algorithm is O(n^2), but how would we go about finding some constants c1, c2 to prove f(n) is big-0 and little-0 of 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++;

Upvotes: 1

Views: 1458

Answers (3)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

To formally deduce the order of growth, you may proceed like the following:

enter image description here

For the c' case, the inner loop won't execute when i = 0, therefore, the solution is to externalize the outer loop "iterations" that won't affect the inner loop.

Upvotes: 2

hlu
hlu

Reputation: 1

Both code blocks represent O(n^2)

1st block should is a typical example of n^2 complexity. Inner and outter loops are traversing N times.

2nd block is also n^2 even though the inner loop breaks earlier than the 1st block would on small i's. If you print out the i and j you'll see that this loop represents the combination pairs of i and j ... i.e. (1,0),(2,0),(2,1),(3,0),(3,1),(3,2) etc

Upvotes: 0

Sam I am says Reinstate Monica
Sam I am says Reinstate Monica

Reputation: 31184

Both of those are O(n2)

Your code has a handy mechanism for measuring the time complexity, and that is the sum variable

Go implement that with different values for n. if your sums make a line, it's linear. if they don't it's not linear. I think that you'll find that in your first algorithm, sum will always be exactly n^2

Upvotes: 1

Related Questions