I need to multiply an array A by it self. Is there an algorithm that does
array multiplication with complexity O(n^2)?Doesn't it take at least O(n^3)?
On Sun, Jan 20, 2013 at 12:44 AM, Dave dave_and_da...@juno.com wrote:
@Guneesh: I think you mean to say that the complexity of both the
not possible unless u use augmented bst..which itself takes o(n) to built
--
This is a test This is a programming test This is a programming test in any
language
1 1 1 122 2 2 233 3 3
3 3 33(count of this)
0 0 1 111 2 2 222 3 3
3 3 3
How to check if polygon is simple based on given list of points ?
--
http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way
On Sun, Jan 20, 2013 at 4:57 PM, Guneesh Paul Singh gunees...@gmail.comwrote:
not possible unless u use augmented bst..which itself takes o(n) to built
--
--
If for all the nodes in BST we also store the size of subtree, then it is
possible to find nth smallest element in O(logN).
On Sun, Jan 20, 2013 at 4:57 PM, Guneesh Paul Singh gunees...@gmail.comwrote:
not possible unless u use augmented bst..which itself takes o(n) to built
--
--
@Koup: No, I meant O(n^3 log k). Sorry.
Dave
On Sunday, January 20, 2013 3:09:00 AM UTC-6, Koup wrote:
I need to multiply an array A by it self. Is there an algorithm that does
array multiplication with complexity O(n^2)?Doesn't it take at least O(n^3)?
On Sun, Jan 20, 2013 at 12:44 AM,
@Shady: See http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm.
Dave
On Sunday, January 20, 2013 10:02:19 AM UTC-6, shady wrote:
How to check if polygon is simple based on given list of points ?
--
to make it O(n logn)
1.Chose one index O(n)
2.For this index do a bsearch on remaining array to find the postion
bsearch can be done as the array is an increasing function(it donotes no
of occurrence of each word,so=previous index value)
bsearch will be done like this
1.make a new temp array that