What is the order of growth of the running time for your implementation of function edit_distance in the best case and in the worst case? Express your answers using Big- notation.

int edit_distance (string A, string B) { m = A.length(); n = B.length(); for (int i = m; i >= 0; i--) { for (int j = n; j >= 0; j--) { if (i == m) d[i][j] = 2 * (n - j);

else if (j == n) d[i][j] = 2 * (m - i);

else if (A[i] == B[j]) { d[i][j] = d[i + 1][j + 1]; }

else d[i][j] = min(2 + d[i][j + 1], min(2 + d[i + 1][j], 1 + d[i + 1][j + 1]));

} }

return d[0][0];

}