Insertion Sort Advanced Analysis

  • + 18 comments

    Thanks for the awesome problem HR! I foolishly thought this was going to be as easy as the first couple and quickly got stuck (trying to use a brute force insertion sort method, with O(n^2) complexity. Though frustrating at the time, good idea to include test case file #7 to throw off unbalanced implementations. To give some hints to others following my path: 1. To solve this problem, take each element e in the array and add up all previous numbers in the array greater than this number. 2. The aggregate of all these sums is your output. To achieve this result, you'll need to research some computing concepts. In order, I recommend: - Binary Search Trees (http://en.wikipedia.org/wiki/Binary_search_tree) - AVL trees, aka, balanced binary search trees (http://www.geeksforgeeks.org/avl-tree-set-1-insertion/) - Order statistic trees, specifically the rank method (http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree) Good Luck! PS Mods, if this is too many hints, let me know and I can take it down.