Defining as a function of n how often an operator is executed that increments the variable counter

Question

Well, that’s why I am new to the analysis of algorithms and I will be very grateful for any useful tips that you can share with how to do this. I am trying to determine how many times the count increases depending on n. I ran it in the idea, and for values ​​1-7 - 1,3,6,10,15,21,28. I just don't know how to write this as a function of n? Thank you The loop is as follows:

for(int i = 1 ; i <= n ; i++){ for (int j = 1 ; j <= i ; j++) { count++; } } 

Answer 1

The goal of this exercise is to teach how you analyze it on paper, rather than running it on a machine. But look at the template:

• The outer loop will execute a total of n times
• The inner loop will run from 1 to n times, depending on what i is at the moment. But you know that on average this will work (n+1)/2 times.
• So count = n(n+1)/2) , which is O(n^2)

See

Update: As requested - why the inner loop is (n+1)/2 :

The outer loop will increment i between 1 and n. Therefore, at each iteration of the outer loop, the inner loop will “loop” a little more than before.

Thus, the inner loop will repeat this number of times:

• 1 + 2 + 3 + ... + n

So, we can do something smart and put together:

• n s 1: (n + 1) = n + 1
• n-1 s 2: (n - 1) + 2 = n + 1
• n-2 s 3: (n - 2) + 3 = n + 1
• ...

And since we pair them, we have n / 2 pairs like these:

• So, the sum 1 + 2 + ... + n is equal to ((n + 1) * (n / 2)).
• Thus, the average value ((n + 1) * (n / 2)) / n = (n + 1) / 2

(Visualize it when you write 1 + 2 + 3 + ... + n on a long strip of paper and you fold it in half.)

I also highly recommend reading this famous story about Karl Friedrich Gaus , so you will always remember how to summarize arithmetic series =)

Answer 2

1

1 + 2 = 3

1 + 2 + 3 = 6

1 + 2 + 3 + 4 = 10

1 + 2 + 3 + 4 + 5 = 15

Only I see the template ?:-)

Answer 3

Here you go:

count = n * (n + 1) / 2