Queries with Fixed Length

  • + 0 comments

    why is complexity O( QN)? i think it's O(N). I guess the worst case is 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 ... where Q=5. Only at 5, we need 4 comparisions, because 4 3 2 1 are in the queue, but we only have N/Q 5, and thus (Q-1)* N/Q is about N. What do you think?