Big O - Algorithm Analysis

• March 15th, 2012, 06:48 PM
PeskyToaster
Big O - Algorithm Analysis
How do I analyze a for loop that looks like

for (j = 0; j < 2*n; j += 2)

I know that if it was just j++ it would loop 2n times but the += is throwing me off. This loop is nesting in a normal loop of

for(i=0; i < n; i++)

I know this will make it n^2 but I don't know how the j += 2 affects the time.

Thanks for the help,
PeskyToaster
• March 15th, 2012, 06:53 PM
Tjstretch
Re: Big O - Algorithm Analysis
Code Java:

`j += 2`
just adds 2 to j, it is the same as
Code Java:

` j = j + 2`
, and because j is incrementing twice every loop, it is going to reach it's end twice as fast, so it is going to be looping
Code :

`1/2 * 2n`
or
Code :

`n`
times.
• March 15th, 2012, 06:56 PM
newbie
Re: Big O - Algorithm Analysis
That loop is the same as for (int index = 0; index < N; index++) in terms on time complexity.
• March 15th, 2012, 07:36 PM
pbrockway2
Re: Big O - Algorithm Analysis
And, does the factor of 2x or 0.5x or whatever was worrying you, really matter?
• March 16th, 2012, 12:48 AM
PeskyToaster
Re: Big O - Algorithm Analysis
I have another problem. First here's the code snippet. It's just general code for analysis

Code Java:

```  for (j=0; j<2n; j++) { i = 1; Generic Statement; while (j<n) { Generic statement; Generic statement; i = i *2; } }```

How does the i = 2n and the j < 2n affect the Big O and execution time. The execution time is just the equation with each statement being one time unit.