We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I'm going to preempt any response you plan to give since your claim bugs me.
This problem is a slight variation of the summing all sub-matrices of size m x m in an n x n matrix. The variations are 1) the sub-matrix (hourglass) has a fixed size (3 x 3) and 2) we don't sum the entire matrix since it's an hourglass. That's the only reason the summing part is a constant factor.
If we altered this problem to say n is always even and the hourglass is always n/2 the complexity would then be O(n^4) because the innermost loop would be a function of n. So, we'd end up with:
(n - (n/2 - 1))^2(n/2)^2 = O(n^4)
In fact, if we take this problem back to the one it's a variation of, drop the hourglass constraints, and allow for any sub-matrix of size m x m in an n x n matrix such that n > m the non-dynamic solution has a complexity of O(n^2m^2). Because we'd then have:
(n - (m - 1))^2m^2 = O(n^2m^2)
That's my line of thought about the complexity. The only way I see O(n) being reasonable is if you consider n to be fixed and the (n - 2)^2 part to be a coefficient on n but, aside from that being uninteresting analysis, that neglects the fact the coefficient is actually a function of n with greater significance.
If you like, please respond with the math you came up with to get O(n) complexity.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Day 11: 2D Arrays
You are viewing a single comment's thread. Return to all comments →
I'm going to preempt any response you plan to give since your claim bugs me.
This problem is a slight variation of the summing all sub-matrices of size m x m in an n x n matrix. The variations are 1) the sub-matrix (hourglass) has a fixed size (3 x 3) and 2) we don't sum the entire matrix since it's an hourglass. That's the only reason the summing part is a constant factor.
If we altered this problem to say n is always even and the hourglass is always n/2 the complexity would then be O(n^4) because the innermost loop would be a function of n. So, we'd end up with:
(n - (n/2 - 1))^2(n/2)^2 = O(n^4)
In fact, if we take this problem back to the one it's a variation of, drop the hourglass constraints, and allow for any sub-matrix of size m x m in an n x n matrix such that n > m the non-dynamic solution has a complexity of O(n^2m^2). Because we'd then have:
(n - (m - 1))^2m^2 = O(n^2m^2)
That's my line of thought about the complexity. The only way I see O(n) being reasonable is if you consider n to be fixed and the (n - 2)^2 part to be a coefficient on n but, aside from that being uninteresting analysis, that neglects the fact the coefficient is actually a function of n with greater significance.
If you like, please respond with the math you came up with to get O(n) complexity.