Serving the Quantitative Finance Community

 
User avatar
FritzJacob
Posts: 3
Joined: January 22nd, 2010, 11:15 am

Matrix brainteaser

November 9th, 2013, 4:40 pm

Few feed back comments received saying the earlier post was very cryptic.Pls find an attachment of an example, how this algo works. Edited earlier post to map to this example at each step.
Attachments
MatrixBrainTeaser_V2.png.zip
(88.27 KiB) Downloaded 79 times
 
User avatar
FritzJacob
Posts: 3
Joined: January 22nd, 2010, 11:15 am

Matrix brainteaser

November 14th, 2013, 1:56 am

Here is one paper (Year 2004) which is close to the solution I proposed. Even though the author's claim the complexity is O(x*y) = O(n)...I am not sure about that after reading the paper. There is some "staircase" work involved at each cell, which will add to the complexity, which is ignored as negligible. I am not sure if I am being a bit biased towards the solution given in this forum ;-)http://dl.acm.org/citation.cfm?id=996820Here is another one (Year 2010) which says the fastest existing algorithm is O(n * (log(n))^2)http://arxiv.org/abs/1004.0558Wikipedia link.http://en.wikipedia.org/wiki/Largest_em ... *******Can someone please point me to a faster solution than these?I am trying with some academic profs, yet to get any responses.The solution proposed here in this forum is of complexity (O(n*log(n)).