Found this simple and basic explanation for Big-O notation. Enjoy.

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Found this simple and basic explanation for Big-O notation. Enjoy.

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

NirmalaNice. Making Big-O not so intimidating!

NirmalaFollowing our chat on reducing complexity of algorithms by becoming context-aware – I came across this analysis called – amortised cost analysis which is different from the worst case analysis that the big-O notation represents. This provides worst case guarantees but does an average-case analysis – somewhat like all the savings we get from a “normal” operation can be sort of saved up and used for an occasional case of managing the worst case of the operation. We could include arguments along similar lines to strengthen our case, I guess.

ravisatzodaPost authorPlease share the link or details on the amortized cost analysis. Will be useful for other also. Thanks.

NirmalaRavi, I read about it here: http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec20-amortized/amortized.htm.

There is also this paper that seems to apply this analysis for real-time scheduling: http://www2.tcs.ifi.lmu.de/~jost/research/FM09_AmortisedAnalysis__Jost_etAl.pdf