On Jan 31, 11:17 am, ritu <ritugarg.c...@gmail.com> wrote:
> @Ralph
> "Build a data structure on array B[1..n] in O(n) time such that
>
> > the following problem can be solved in O(log n) time:
> > Given an index i and value v, find the index j of the first
> > element in B such that j >= i and B[j] > v.
> > Return -1 if no such j exists.
> > "
>
> then it ll take n*lg(n) time ... while a o(n) solution exists
Your comment makes no sense given that I posted a (slightly)
different problem. In the original problem there is no "v"!
Of particular importance the value v is not provided until after
the data structure is constructed. For the record the O(log n) time
cost for a query is optimal. (Admittedly I never actually proved
this.)
Regards,
Ralph Boland
>
> On Jan 31, 9:25 pm,RalphBoland<rpbol...@gmail.com> wrote:
>
> > On Jan 30, 11:00 pm, ritu <ritugarg.c...@gmail.com> wrote:
>
> > > You are given an array (unsorted) and for every element i, find the
> > > first occurance of an element j (in the remaining array) that is
> > > greater than or equal to i. If no such j occurs then print -1.
> > > Eg: Input---> A={1,3,5,7,6,4,8}
> > > Output---> 3 5 7 8 8 8 -1
> > > Time Complexity:O(n)
> > > Space Complexity:O(n)
>
> > I solved a version of this problem in my thesis.
>
> > Build a data structure on array B[1..n] in O(n) time such that
> > the following problem can be solved in O(log n) time:
> > Given an index i and value v, find the index j of the first
> > element in B such that j >= i and B[j] > v.
> > Return -1 if no such j exists.
>
> > I have an application of this data structure in my thesis (which
> > is why I invented it) but I would love to hear other applications.
>
> >RalphBoland
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
