-
Why isn’t Time Complexity of the Tromino Algorithm O(n⁴)
Without deeper thought, one might easily assume the time complexity of the tromino algorithm is O(n^4). This is because the algorithm divides the matrix into 4 smaller subproblems, suggesting a recursive solution that calls itself 4 times. However, this is not the case. The actual time complexity of the algorithm is O(n^2). Let’s explore why.…
