Re: divide & conquer algorithm to implement string matching

On 30 Mag, 14:44, misterio <giagim...@xxxxxxxxx> wrote:
It should be noted that this approach is extremely unfruitful!Let n be
the lenght of the main string and m the lenght of the pattern to
search on the main string.This algorithm has a time complexity of
O(O(m) * (n * O(m))),that is,if O(m) is proportional to O(n),this
gives an O(n^3) time complexity.A really really really bad algorithm.
P.S. The (n * O(m)) should be something like ((2n - 1) * O(m)), if I
consider to stop at partitions of 1 element and not 4,so I tried cut
some constant multiplicator,but it's irrelevant.
This is wrong,because I solved the recurrence without thinking that m
is varying,so in the divide sequence I divide less if m is bigger.So
maybe the time complexity is inferior,I'm not sure.

.

Relevant Pages

  • Re: divide & conquer algorithm to implement string matching
    ... the lenght of the main string and m the lenght of the pattern to ... search on the main string.This algorithm has a time complexity of ... gives an Otime complexity.A really really really bad algorithm. ...
    (comp.programming)
  • Re: Maximum value of a function...
    ... I have a cost function which has two parameters as inputs, ... The cost function is actually the time complexity of an algorithm and ... Complexity of the algorithm is: ... So now I'm stuck. ...
    (sci.math)
  • Re: Another twin primes conjecture
    ... > algorithm could be made faster, but that the time complexity of his ... > algorithm was not good enough. ... Not only pointers. ... determine a huge number of values quicker by using a sieve and therefore ...
    (sci.math)
  • Re: Quicker then QuickSort???
    ... Thank you for the information about the time complexity! ... Kristofer Gafvert - IIS MVP ... i cannot tell you the Ofor this algorithm (because i am ... > are sorting 30 things, an n^2 algorithm may go faster, but when sorting ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: find the largest 1000 values
    ... I have a new idea of using STL nth_element algorithm, and each time I read a number of data which my memory can afford, then I input to nth_element which could save time to sort. ... I am wondering the time complexity of nth_element, ...
    (microsoft.public.vc.language)