Java programming question.

[digisatman]

Hi all,

Revising for my course and got a question that Im not sure about:

Given the following java program segment

_______for (int i=0;i < n-2;i++)
_________for (int j=i+1;j < n-1; j++)
__________for (int k=j+1; k < n; k++)
_____________System.out.println(i + “ “ + j + “ “ k);

Q.how many times is the print statement executed? Explain your answer.

Can anyone here help me understand this please?

Thanks

 

[Inquisitor]

You need to calculate how many times each of the inner loops is going to iterate per iteration of its parent loop. The outer loop will iterate n - 2 times, but for the two inner loops, it's going to depend on how many iterations the respective parent loop has made so far.

The k-loop will iterate n - (j + 1) times per iteration of its parent and the j-loop will iterate n - 1 - (i + 1) times, also per parent iteration.

So, first off, you can calculate the number of times the j-loop will execute by evaluating n - 1 - (i + 1) for all values of i that the outer loop will pass through and then adding them all together. Once you've done that you can do the same for the k-loop and this will give you the number of times the output is printed.

Does seem like a bit of a long-winded question though. Are you sure n isn't given?

 

[digisatman]

hi thanks for that, looks confusing!

n is definetly not given!

ran it thru the compiler with some values of n:

n = 0 output = 0
n = 1 output = 0
n = 2 output = 0
n = 3 output = 1
n = 4 output = 4
n = 5 output = 10
n = 6 output = 20
n = 7 output = 35

still not getting it.

 

[mattgaunt]

I think your meant to be finding the time complexity of the algorithm perhaps?

Cos basically that function will grow exponentially, Im not sure of how to calculate the no. of times the print statement in printed but my guess is the base case is n > 2 (When the function will actually work) and that it has time complexity containing a logarithm, but my time complexity was never that great so i could be wrong

Anyway if u write out the loops on paper for n = 4 n = 5 n = 6 you do start to see a pattern and u can see why it grows exponentially but I can't get my head around how you put that into a formula for the number of times the print statement is printed.

Gaunt

 

[Dj_Jestar]

What a pants programming question.

 

[roid]

They generally are ;[