@hary: nhin, its some constant multiple of n. O(constant*n) for a string of length n, 2*n-1 positions are there. every time i calculate the next center using prev center value if the value at prev center is a large one then this next center value skips that many positions to compensate.. if the value at prev center is small then next center won't skip positions it may be just the next one. so overall, it gives linear complexity.
On Jul 1, 12:35 pm, hary rathor <[email protected]> wrote: > @Dumanshu; worst case O(n3) hai iska -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
