0
$\begingroup$

Recently, I had to implement the following algorithm (similarly). Code in Kotlin:

fun solution(keyword: String, lyric: String): Boolean {
        val lyricWords = music.split(" ") 
        var index = 0
        for (word in lyricWords) {
          for (c in word) {
            if (c == keyword[index]) {
              index++
              break
            }
            if (index == word.size) return true
        }
        return false
 }

My intuition to the runtime analysis, given n to be the length of lyric and m the length of keyword:

  1. O(n) for the split operation, since it should scan the entire string looking for spaces.
  2. Roughly O(n) for the second for-loop, since it would iterate through all the characters for every word in the worst case.
  3. O(m) for the internal for-loop over all characters in keyword.
  4. Overall, should that take under O(n+m)?

What would be the time complexity for the above function?

$\endgroup$
2
  • 1
    $\begingroup$ Assuming a reasonable implementation of split(), constant-time access to each element the collection lyricWords, and constant-time access the $i$-th character in a string, the time complexity would be $O(n)$. Notice that if $m = \omega(n)$ you still do only $O(n)$ iterations of the inner loop. This is tight, in the sense that there are some inputs for which the time spent is $\Omega(n)$. $\endgroup$
    – Steven
    Jun 14, 2022 at 13:37
  • 1
    $\begingroup$ 1. Coding questions are off-topic here, and analyzing the running time of a chunk of code generally requires information that is beyond the scope of this site (e.g., the running time of various programming language primitives, like in). Not everyone here knows Kotlin, and the details of Kotlin are off-topic here. We'd prefer that you share your code as concise pseudocode. 2. What attempts have you made? See cs.stackexchange.com/q/23593/755 for the general approach. $\endgroup$
    – D.W.
    Jun 14, 2022 at 17:58

1 Answer 1

1
$\begingroup$

For loop inside For loop indicates multiplication of time complexity parts.

For loop following for loop indicates addition of time complexity parts.

So I'd expect: $O(mn)$

That is to say. You doing $O(m)$, $n$ number of times. Thus $O(mn)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.