Programming Forums - View Single Post - Challenging Programming Problem

Sane · Dec 30th, 2007, 6:43 AM

The problem with that... is upon worst case, an unbalanced binary tree takes N operations to inject... O(N^2).

So you have to balance it via tree rotations (my solution) O(logn + k) x N = O(nlogn + nk) = O(nlogn). It's not a very quick thing to implement, and the professor said there are better tricks with DP.

Try it.

Dec 30th, 2007, 6:43 AM	#3
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,886 Rep Power: 5	Re: Challenging Programming Problem - "Pinball Ranking" The problem with that... is upon worst case, an unbalanced binary tree takes N operations to inject... `O(N^2)`. So you have to balance it via tree rotations (my solution) `O(logn + k) x N = O(nlogn + nk) = O(nlogn)`. It's not a very quick thing to implement, and the professor said there are better tricks with DP. Try it.