0
$\begingroup$

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 enter image description here 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."?

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

1 Answer 1

0
$\begingroup$

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 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.