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.
This is the basically same solution I worked out, and I don't know how to do it better, but I want to register my disagreement with the O(n * m) complexity.
The problem specifically dictates that the inner arrays are the same length as the outer arrays. If n = m, then n*m is the same thing as n^2. If the array lengths were variable & there were no restriction that n = m, then this would be O(n*m), but for the problem that actually exists it's definitely O(n^2). Furthermore, Big O notation usually specifies a worst-case scenario.But for this implementation of this problem, the worst case scenario is EVERY scenario. This solution will always take n^2 time, because there is no way for it to ever return before it's completed both n-length loops. It's intellectually dishonest to label the solution O(n*m) to make it look more efficient than it actually is when you know damn well it's exponential.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
2D Array - DS
You are viewing a single comment's thread. Return to all comments →
This is the basically same solution I worked out, and I don't know how to do it better, but I want to register my disagreement with the O(n * m) complexity.
The problem specifically dictates that the inner arrays are the same length as the outer arrays. If n = m, then n*m is the same thing as n^2. If the array lengths were variable & there were no restriction that n = m, then this would be O(n*m), but for the problem that actually exists it's definitely O(n^2). Furthermore, Big O notation usually specifies a worst-case scenario.But for this implementation of this problem, the worst case scenario is EVERY scenario. This solution will always take n^2 time, because there is no way for it to ever return before it's completed both n-length loops. It's intellectually dishonest to label the solution O(n*m) to make it look more efficient than it actually is when you know damn well it's exponential.