Search a word in a matrix runtime comlexity

Question

Trying to analyze the runtime complexity of the following algorithm:

Problem: We have an $m \cdot 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 \cdot n \cdot 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 \cdot 3^{(l - 1)} + 4 + 4 \cdot 4 + 4 \cdot 3 \cdot 4 + ...$

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

Answer 1

Let $T(l)$ denote the time it takes to search for a string of length $l$, and let $T'(l)$ be the time it takes to search for a string of length $l$ when one direction has been eliminated. Then $$ T(l)=4T'(l-1)+c,\\ T'(l)=3T'(l-1)+c $$ where $c$ is $O(1)$, and includes the time it takes to check if the square is visited, mark the square as visited, and compare the current letter against $s$.

We solve the second recurrence for $T'$, and plug that solution in to the first equation to get $T$.

$$ T'(l)=c(1+3+3^2+\dots+3^{(l-1)})+3^{l}\cdot T(0)=c\cdot \frac{3^l-1}{2}+3^l\cdot T(0) $$ so you still get $T'(l)=O(3^l)$, and the same for $T(l)$. Note that the $+c$ only adds another factor of $3^l$, so it does not change the asymptotic runtime.