striker_46's blog

time complexity of lps
By striker_46, history, 2 weeks ago, In English

I am learning the alogorithm of prefix_function i get the algorithm but unable to understand the time complexity of the algorithm why the time complexity is o(n) can anyone explain the time complexity of algo.

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

TC:O(n) AND NOT O(n^2) since the decrease in the LPS is bounded by the increase and increase is very gradual so worst case O(2n)

→ Reply