http://ayende.comAyende @ RahienCopyright (C) Ayende Rahien 2004 - 2021 (c) 202660I get your point. Though I still don't agree. Anyway, you use big o notation to discuss the complexity of the algorithm. N in the O(N^3 + N) barely adds anything to the overall time complexity. http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment12http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment12Thu, 24 Dec 2009 11:29:57 GMTWe have.. 1. Outer loop - O(N) 1.a. Linq query - O(N) 1.b OrderedCollection.Add - O(N) 2. StatementChanged - O(N) Now the Linq query and the OrderCollection.Add are in the scope of the outer loop, so we have O(N*2N+N) which is O(N^2) http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment11http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment11Thu, 24 Dec 2009 09:43:11 GMTVadim, O(N^3 + N) express what is going on better than just N^3. Note the comment in the end of the post. http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment10http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment10Wed, 23 Dec 2009 21:10:46 GMTYep, it's not O(N^3) but O(N^2) like Manu said. If it were O(N^3) the program would probably take 50 years to process 50 000 statements. http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment9http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment9Wed, 23 Dec 2009 19:35:32 GMTarent people reading your post ayende? three comments about n^2 already... http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment8http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment8Wed, 23 Dec 2009 19:26:01 GMTI also think it's O(N^2). The LINQ query takes O(N) and the unfilteredStatements.Add statements takes O(N). This sums up to O(N + N) and not O(N * N) within the foreach loop. http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment7http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment7Wed, 23 Dec 2009 18:30:36 GMTJust my fifty cents. Anyway, why haven't you simply written O(N^3) instead of O(N^3 + N) and O(N) instead of O(N + N)? For me it's confusing to see odd O(N^3 + N) instead of O(N^3). And even more confusing to see this in the post title... http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment6http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment6Wed, 23 Dec 2009 18:02:27 GMTMike, As I said in the post, the collection changed event is making an O(N) operation every time it is invoked. http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment5http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment5Wed, 23 Dec 2009 14:39:38 GMTI think Sebantian is right, this is O(N^2). Unless the CollectionChangedEvent is performing an O(N) operation and for each value of N the subscriber is performing, everything in unfilteredStatements is O(N), not O(N^2). It is O(N), the for loop, operating on N+N+N, the three O(N) statements, which comes out to O(N^2). http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment4http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment4Wed, 23 Dec 2009 14:27:59 GMTSebastian, Note the next statement, unflitedStaetments is firing a CollectionChanged event that has a subscriber that does another O(N) operation http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment3http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment3Wed, 23 Dec 2009 13:00:08 GMT>> At first glance, it looks like O(N*N), right? At second glance, it still does to me. Your loop body is a sequence of two O(n) operations, summing to O(n). So we have a O(n²) loop followed by a O(n) operation, that's O(n²+n) = O(n²). ...whatever - another great example of real world performance improvements! http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment2http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment2Wed, 23 Dec 2009 12:47:08 GMTCan't wait to see these performance improvements in action myself. Keep up the good work! http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment1http://ayende.com/4335/uberprof-performance-improvements-or-when-o-n-3-n-is-not-fast-enough#comment1Wed, 23 Dec 2009 11:09:23 GMT