# What will be the frequency count of this code snippet?

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.

• 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 – nir shahar Mar 26 at 11:24
• Is this typed exactly as its written, or are there possibly some errors in typing it? – awillia91 Mar 27 at 13:40
• This how to question was given to me in my homework. I made no changes – Brishti Basu Mar 28 at 18:55
• $j$ is initialized to what? Without it, no claim can be made. Your homework question is incorrect in that case. – Inuyasha Yagami May 13 at 16:39
• 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. – greybeard May 13 at 17:58

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)

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