Search a word in a matrix runtime comlexity

Question

Trying to analyze the runtime complexity of the following algorithm:

Problem: We have an m * n array A consisting of lower case letters and a target string s. The goal is to examine whether the target string appearing in A or not.

algorithm:

for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
        if(A[i][j] is equal to the starting character in s) search(i, j, s)
    }
}

boolean search(int i, int j, target s){
    if(the current position relative to s is the length of s) then we find the target
    looping through the four possible directions starting from i, j: {p,q} = {i+1, j} or {i-1, j} or {i, j+1} or {i, j-1}, if the coordinate is never visited before
    search(p, q, target s)
}

One runtime complexity analysis that I read is the following:

At each position in the array A, we are first presented with 4 possible directions to explore. After the first round, we are only given 3 possible choices because we can never go back. So the worst runtime complexity is O(m * n * 3**len(s))

However, I disagree with this analysis, because even though we are only presented with 3 possible choices each round, we do need to spend one operation to check whether that direction has been visited before or not. For instance, in java you probably just use a boolean array to track whether one spot has been visited before, so in order to know whether a spot has been visited or not, one needs a conditional check, and that costs one operation. The analysis I mentioned does not seem to take into account this.

What should be the runtime complexity?

update:

Let us suppose that the length of the target string is l and the runtime complexity at a given position in the matrix is T(l). Then we have:

T(l) = 4 T(l- 1) + 4 = 4(3T(l - 2) + 4) + 4 = 4(3( 3T(l -3) + 4) + 4)) + 4 = 4 * 3 ** (l - 1) + 4 + 4 *4 + 4 * 3 * 4 + ...

the +4 is coming from the fact that we are looping through four directions in each round besides recursively calling itself three times.

Doj · Answer 1 · 2020-12-09T02:18:28.703

1

What should be the runtime complexity?

The mentioned analysis is correct and the complexity is indeed O(m * n * 3**len(s)).

For instance, in java you probably just use a boolean array to track whether one spot has been visited before, so in order to know whether a spot has been visited or not, one needs a conditional check, and that costs one operation.

That is correct and does not contradict the analysis.

The worst case we can construct is the matrix filled with only one letter a and a string aaaa....aaaax (many letters a and one x at the end). If m, n and len(s) are large enough, almost each call of the search function will generate 3 recursion calls of itself. Each of that calls will generate another 3 calls (which gives us total 9 calls of depth 2), each of them willl generate another 3 calls (which gives us total 27 calls of depth 3) and so on. Checking current string character, conditional checks, spawning a recursion are all O(1), so complexity of the whole search function is O(3**len(s)).

edited Dec 09 '20 at 02:18

answered Dec 08 '20 at 23:01

Doj

1,244
6
13
19

Thank you for answering, but I do not quite understand why checking current string character, conditional checks, spawning a recursion are all ```O(1)```. If we add them all together I do not think it is still ```O(1)```. I have added an update to explain. – penny Dec 09 '20 at 15:14
@penny Big-O notation does not care about multiplication (or addition) by constants. That is, `O(a*f(n)+b)=O(f(n))` for any `a>0`, `b>0`. See https://stackoverflow.com/a/22188943/11695625 – Doj Dec 09 '20 at 17:48
If that is the case then ```O(T(n)) = O(T(n - 1)) = ... = O(T(1)) = O(1)``` which does not feel quite right. – penny Dec 09 '20 at 18:45
@penny It is indeed not right. Number of parts in the `...` is depending on `n`, so you could actually write the equation if `n` was limited (which means it is essentially a constant). But Big-O notation is about asymptotical analysis, that is `n` may be arbitrary large and the equation does not make sense. You should be possible to write (finite) equation without assumtions on `n` to make it works. – Doj Dec 09 '20 at 19:12

Yilmaz · Answer 2 · 2021-10-02T06:48:02.793

The solution is brute force. We have to touch each point on the board. That makes O(m*n) operation.

Now for each point, we have to run dfs() to check if the word exist. So we get

 O(m * n * timeComplexityOf dfs)

this is a dfs written in python. Examine the time complexity

        def dfs(r,c,i): 
            # O(1)
            if i==len(word):
                return True
            # O(1)
            # set is implemented as a hash table.
            # So, time complexity of look up in a set is O(1)
            if r<0 or c<0 or r>=ROWS or c>=COLS or word[i]!=board[r][c] or (r,c) in path_set:
                return False
            # O(1)
            path.add((r,c))
            # O(1)
            res=(dfs(r+1,c,i+1) or
                 dfs(r-1,c,i+1) or
                 dfs(r,c+1,i+1) or
                 dfs(r,c-1,i+1))
            # O(1)
            path.remove((r,c))
            return res

Since we dfs recursively calling itself, think about how many dfs calls will be on call stack. in worst case it will length of word. Thats why

O ( m * n * word.length)

Search a word in a matrix runtime comlexity

2 Answers2