3 replies to this topic

[jwxie518]

I have a sample code in C++

C1, C2, C3 and etc are just name for running time.

[COLOR=#00008b]int[/COLOR] i, j;    
i = [COLOR=#800000]0[/COLOR];    [COLOR=#808080]// c1[/COLOR] 
j = [COLOR=#800000]0[/COLOR];    [COLOR=#808080]// c2[/COLOR] 
[COLOR=#00008b]while[/COLOR] (i < n)   [COLOR=#808080]// (n+1)  c3[/COLOR] 
{ 
  i++;   [COLOR=#808080]// n c4[/COLOR] 
   [COLOR=#00008b]while[/COLOR] ( j < i)  [COLOR=#808080]// (2+3+....+n+(n+1)  c5[/COLOR] 
   { 
     j++;   [COLOR=#808080]// (1+2+...+n)c6[/COLOR] 
   } 
  j = [COLOR=#800000]0[/COLOR];  [COLOR=#808080]// c7[/COLOR] 
}

Clearly, c1, c2, and c7 are constant. We are not interested in those, and they don't really matter in determing the running time.

What I don't understand is c5 and c6.

Why is it 2+3+4...+n+(n+1) for c5? Why does it start with 2, instead of 1+2+3...+(n+1)???
Note that we can rewrite C5 -> (n*(n-1)/2) + n

For c6, this cominbation can be rewritten as n*(n-1)/2

Initially I thought C6 is n, because C6 depends on two conditions, the first while and second while loop. But since j will always go back to 0, so we are really depending on the first while loop. Because n < n is false, then the j++ wil run maxiumly n-th time.

n = 3
0 < 3, 1, 0 < 1, 1, 0
1 < 3, 2, 0 < 1, 1, 0
2 < 3, 3, 0 < 1, 1, 0
3 < 3 fail.

Can someone please explicitly explain how C5 and C6 are deteremined?
I am sorry if this problem sound dumb to the experts
Thank you!

[Momerath]

Your C5 equation is wrong, it is (n+1)*(n+2)/2-1.

As for your first question, it starts at 2 because the first time through it is checked 2 times. Let's say n = 3 (as your example). First time through we have (0 < 1), second iteration checks (1 < 1), thus it is executed 2 times.

C6 runs 1 less times each iteration than C5 (since it doesn't run when the condition is no longer true) so it's total run time is n*(n+1)/2.

[WingedPanther]

c7 runs n times, not once.

[jwxie518]

Very right. LOL I notice it was way too late to reply! forgive me!

Thanks!