IWETHEY v. 0.3.0 | TODO
1,095 registered users | 0 active users | 0 LpH | Statistics
Login | Create New User
IWETHEY Banner

Welcome to IWETHEY!

IWETHEY Home / IWETHEY Board / Theory and Practice of Programming Forum / Just doing a cursory glance at it...
Post #92,228
by Yendor
3/27/03 3:20:52 PM
Reply
New Just doing a cursory glance at it...
...it looks like O(n^3). There are 3 nested for loops. Yes, they don't all have the same boundary conditions, and that's where I might be getting off a bit. But a triply-nested for-loop sounds like n-cubed to me.

Wonderfully efficient. ;-)
-YendorMike

[link|http://www.hope-ride.org/|http://www.hope-ride.org/]
Post #92,230
by jake123
3/27/03 3:29:44 PM
3/27/03 3:30:15 PM
Reply
New Yeah, I was wondering about that.
The i loop makes the j loop run i times, where i is going to be equal to n + (n-1) + (n-2) + ... + 1 times. In turn, each run of the j loop makes the k loop run i the same number of times. The loop at the bottom for moving the array members around should run on average n/2 times; it's not important, right? So, really you're looking at (n + (n-1) + (n-2) + ... + 1)^2. Yes...?
--\r\n-------------------------------------------------------------------\r\n* Jack Troughton                            jake at consultron.ca *\r\n* [link|http://consultron.ca|http://consultron.ca]                   [link|irc://irc.ecomstation.ca|irc://irc.ecomstation.ca] *\r\n* Kingston Ontario Canada               [link|news://news.consultron.ca|news://news.consultron.ca] *\r\n-------------------------------------------------------------------
Expand Edited by jake123 March 27, 2003, 03:30:15 PM EST
Expand All History
     Fun with complexity - (jake123) - (8) - March 27, 2003, 03:13:05 PM EST
         Just doing a cursory glance at it... - (Yendor) - (1) - March 27, 2003, 03:20:52 PM EST
             Yeah, I was wondering about that. - (jake123) - March 27, 2003, 03:30:15 PM EST
         OK, a bit less of a cursory glance... - (Yendor) - (3) - March 27, 2003, 03:44:05 PM EST
             Yes, I've come to that conclusion too - (jake123) - (2) - March 27, 2003, 04:27:19 PM EST
                 Just so you know - (jake123) - (1) - March 28, 2003, 09:13:53 AM EST
                     Glad to help! :) -NT - (Yendor) - March 28, 2003, 09:30:14 AM EST
         my favourite sort algorithm is... - (cforde) - (1) - March 28, 2003, 12:16:38 AM EST
             Freak -NT - (tuberculosis) - April 8, 2003, 04:00:51 PM EDT

Home of the sash-swinging flasher!
46 ms