再帰を用いたプログラムの計算複雑度について

ある面で、最も広い面積の正方形の辺の長さを求めるプログラムを書いています。
入力された配列の要素が0なら黒、1なら白とし、白の面積が最大となる場合の１辺の長さを出力します。

困っていること
動的計画法で書いた再帰表現を含むプログラムを実行しているのですが、計算複雑度のオーダを考える時に、最悪の場合「square(M, i+1, j+1) + 1 」が何回繰り返されるかに依存すると考えられます。

行列Mの縦横i,jの内、長い方ということになるでしょうか。
3x4行列であれば、O(4)で、一般化するとCが定数でO(C)という理解で合っていますか。
もし間違っていたらご指摘いただきたいです。

プログラム

def square(S, i, j):
    max = 0
    if S[i][j]== 0:
        return 0
    elif S[i][j]==1 and S[i+1][j]==1 and S[i][j+1]==1 and S[i+1][j+1]==1:
        return square(S, i+1, j+1) + 1 
    return 1

i = 2
j = 1

S= [[0, 1, 1, 0, 1], 
    [1, 1, 0, 1, 0], 
    [0, 1, 1, 1, 0], 
    [1, 1, 1, 1, 0], 
    [0, 0, 0, 0, 0]] 


print(square(S, i, j)) #2