Programming Forums > Application Development > C++

panzerss · Mar 19th, 2005, 7:19 AM

What would be the time complexity (accurate) of the following?
n=number of elements
...
for(i=0;i<n-2;i++)
for(j=i+1;j<n-1;j++)
for(k=j+1;k<n;k++)

Now if were there just i and j loop the accurate time complexity would be n^2-n/2 but with the third loop i get a bit confused.
PLEASE HELP!!!

tempest · Mar 19th, 2005, 9:11 AM

I'm sorry, is english your native language. I can't understand what you are trying to say. You've confused the hell out of me.

If you are asking how long that code will slow down your program, which i think you might be, then if n is a number greater than 10 you'll be able to see a difference.

Ooble · Mar 19th, 2005, 12:15 PM

I think he wants the Big O of that loop.

panzerss · Mar 19th, 2005, 2:01 PM

Take this for instance that you have some if statement in the core of the loops:

for(i=0;i<n-2;i++)
for(j=i+1;j<n-1;j++)
for(k=j+1;k<n;k++)
if(something is something blabla)

How many times would the if statement be executed???

kurifu · Mar 19th, 2005, 5:21 PM

Big O should be the same, since they are all linear equations (I actually forget how to spell that word).

These for statements would have varying complexity (if by complexity you mean big O)

(Toggle Plain Text)

for( ;; );
for( int i = 0; i < n; i++ )
for( int i = 0; i < n; i *= 2 )

First one never converges, second one converges linearly, and the third converges at a rate of O(2) or something like that.

Mar 19th, 2005, 7:19 AM	#1
panzerss Newbie Join Date: Mar 2005 Posts: 2 Rep Power: 0	Time Complexity Problem What would be the time complexity (accurate) of the following? n=number of elements ... for(i=0;i<n-2;i++) for(j=i+1;j<n-1;j++) for(k=j+1;k<n;k++) Now if were there just i and j loop the accurate time complexity would be n^2-n/2 but with the third loop i get a bit confused. PLEASE HELP!!!

Mar 19th, 2005, 9:11 AM	#2
tempest Programming Guru Join Date: Oct 2004 Posts: 1,041 Rep Power: 6	I'm sorry, is english your native language. I can't understand what you are trying to say. You've confused the hell out of me. If you are asking how long that code will slow down your program, which i think you might be, then if n is a number greater than 10 you'll be able to see a difference. __________________

Mar 19th, 2005, 12:15 PM	#3
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	I think he wants the Big O of that loop. __________________ Me :: You :: Them

Mar 19th, 2005, 5:21 PM	#5
kurifu Expert Programmer Join Date: Jul 2004 Location: Halifax, Nova Scotia (Canada) Posts: 784 Rep Power: 5	Big O should be the same, since they are all linear equations (I actually forget how to spell that word). These for statements would have varying complexity (if by complexity you mean big O) (Toggle Plain Text) for( ;; ); for( int i = 0; i < n; i++ ) for( int i = 0; i < n; i = 2 ) for( ;; ); for( int i = 0; i < n; i++ ) for( int i = 0; i < n; i = 2 ) First one never converges, second one converges linearly, and the third converges at a rate of O(2) or something like that. __________________ Clifford Matthew Roche <geek@cliffordroche.com> Web Hosting: http://www.crd-hosting.com Consulting: http://www.crdev-consulting.com

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Mar 19th, 2005, 2:01 PM	#4
panzerss Newbie Join Date: Mar 2005 Posts: 2 Rep Power: 0	Take this for instance that you have some if statement in the core of the loops: for(i=0;i<n-2;i++) for(j=i+1;j<n-1;j++) for(k=j+1;k<n;k++) if(something is something blabla) How many times would the if statement be executed???

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Time Complexity Problem