# Big O analysis trying to follow a logic

Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."? I am trying to follow the logic of the solution provide while myself have a different approach. Here is my thinking (questions state below):

The inner for loop runs m times from 1 and the outer for loop runs n times from 1. Moreover, for each inner loop, m is increased by 2 based on previously additions and m starts at 1. With all these observations, plug in n = 1, print (j) get executed 3 times; n = 2, print(j) get executed 8 times. n = 3,print(j) get executed 15 times. We calculate the sequence to be 3,8, 15..... which has the closed form as 2 n +$$n^ 2$$ . Or by asymptotic run time as Θ( $$n^2$$ )

  fun(n)
m = 1
for i = 1 to n
m = m + 2
for j = 1 to m
Print(j)


Solution: The assignment m=1 takes constant time. The line m = m + 2 is run n many times, which takes Θ( n ) time. The inner print statement runs m many times, and m = 2n + 1 for each n. The total number of times the print statement runs is Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."? How can we draw the connections with "the line m = m+2 is run m many times.." and "the inner print statement runs m many times" to get "and m = 2n+1 for each n."?

• @Apass.Jack, I just realized, i have to click the check mark to consider accepted an answer. Thank you. – Maxfield Dec 12 '18 at 1:55
• I am pleased to see that you have grown your reputation as well as maintain a positive question record. Also the scholar badge! – John L. Dec 12 '18 at 2:19

Possibly it's not for each $$n$$, but for each $$i$$.

First, try to calculate $$m$$ for each specific $$i$$:

 i | m
-------
1 | 3
2 | 5
3 | 7
4 | 9
:
n | 2n+1


$$m$$ increased by two for each loop of for i = 1 to n. Therefore $$m = 2i+1$$ for each $$i$$ in the loop.

And this is repeated from $$i = 1$$ to $$i = n$$, so in total,

$$\sum_{i=1}^n (2i + 1) = n^2 + 2n$$