[KYA]

@quophyie

1. It iterates 12 times so the exactly growth rate is stable, you "could" say O(12) or O(1)

2. yes, log(n) means you need to raise that number to a certain power to get that number. The smallest way to get log(n) is to multiply the increment by 2 (larger numbers also work and probably have a more exact answer, but I lump them into log(n)).

3. That is an infinite loop.

4. No idea. It's a typo, I'll fix it.

5. It's only O(n) if it iterates 'n' number of times, where 'n' is the # of elements in the data structure. Since we're multiplying n by itself we now iterate O(n^2) times.

[xTorvos]

KYA, on 12 September 2009 - 04:03 PM, said:

for(int i = 0; i < n; i *= 2) {
	cout << i << endl;
}

for(int i = 0; i < n; i++) { //linear
	for(int j = 0; j < n; j *= 2){ // log (n)
		//do constant time stuff
	}
}

Last time I checked (about 1.5 minutes ago), taking 0 * 2 gives me 0. I'm thinking your Big O is a little more than log(n).

[KYA]

xTorvos, on 30 March 2010 - 09:42 PM, said:

Last time I checked (about 1.5 minutes ago), taking 0 * 2 gives me 0. I'm thinking your Big O is a little more than log(n).

Fixed.


@quophyie glad you found it helpful.

[macosxnerd101]

Technically, it's O(n^3) as you have three nested for loops making n iterations. But it is bounded by O(n^k).

[ThePheonix21]

Just a question, would an if statement nested inside a while loop be considered a nested statement or a sequential statement?
For example:

while(x!=0){
        if(y>z){
           i++;
         }
       }

That's the one thing I noticed wasn't really noted.

[macosxnerd101]

It's additive in regards to efficiency, so it is a constant, and constants are dropped when calculating Big-O.

[KYA]

Alternatively, you could view conditionals constant as well. (Unless said conditional calls a function or such that is known to be a certain runtime, i.e. strlen(), sizeof(), etc...

[ThePheonix21]

So, a series of If Else statements would be additive as well.

Like:

 if(x==0){
          y++;
       }
       else if(x>0){
          y--;
       }
       else{
         return 0;
       }

macosxnerd101, on 05 September 2010 - 07:00 AM, said:

It's additive in regards to efficiency, so it is a constant, and constants are dropped when calculating Big-O.

This post has been edited by ThePheonix21: 05 September 2010 - 11:07 AM

[macosxnerd101]

Yes, but for Big-O they are irrelevant as they are constants, and they will get dropped at the end.