-1
$\begingroup$
int i=0,j;

while(i<=n)
{
 while(j<=(i+1)){ 
   a=a*a;
    j++;
  }
i++;

This question was in my homework and we have to calculate the frequency count of the code above. I am having difficulty understanding how the code will execute and how many times will the loops execute. I know the inner loop is dependent on 'i', otherwise I'm lost.

$\endgroup$
5
  • $\begingroup$ Do you reset $j$ before the second while loop? If not, then the second loop will take only one operation, since $j$ would already be incremented a big nch of times $\endgroup$ – nir shahar Mar 26 at 11:24
  • $\begingroup$ Is this typed exactly as its written, or are there possibly some errors in typing it? $\endgroup$ – awillia91 Mar 27 at 13:40
  • $\begingroup$ This how to question was given to me in my homework. I made no changes $\endgroup$ – Brishti Basu Mar 28 at 18:55
  • $\begingroup$ $j$ is initialized to what? Without it, no claim can be made. Your homework question is incorrect in that case. $\endgroup$ – Inuyasha Yagami May 13 at 16:39
  • 1
    $\begingroup$ Please see How do I ask a Good Question?/How do I ask a Good Homework Question? I am having difficulty understanding how the code will execute and how many times will the loops execute. Starting with unbalanced braces? If completed&interpreted as a snippet in a "C-like" programming language, it "invokes undefined behaviour" for lack of initialisation of j, if not a. Without anything being used, an "optimising compiler" would conceivably "optimise everything away", emit no code. $\endgroup$ – greybeard May 13 at 17:58
-1
$\begingroup$
Statement         Frequency Count
int i=0,j                1
while(j<=(i+1))         n+1
 a=a*a                   n
 j++                     n
i++                      1  

f(n) = 3n+3 = Time Complexity
Degree is O(n)

Space:
a = n
i = 1
j = 1
S(n) = n+1 = Space Complexity
Degree is O(n)

$\endgroup$
1
  • $\begingroup$ Space [needed for] a = n please elaborate on this. $\endgroup$ – greybeard May 13 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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