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.
Your culling methods do definitely make your algorithm run faster, but only by a constant factor. We can say that your culling method weeds out some percentage of the substrings to check. Let's say it weeds out half, just so we have a number to work with. If you match 0.5N substrings, that takes O((0.5N)^2) = O(0.25N^2) = O(N^2) time, and each comparison takes O(N), so it still takes O(N^3), even though it's four times faster than it would be without the culling. What I can do some time is download your code, make some random input strings of different lengths and do experimental complexity analysis of both solutions. I'll post an excel sheet with the results in a couple of days.
I like this discussion. It's interesting.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and Anagrams
You are viewing a single comment's thread. Return to all comments →
Your culling methods do definitely make your algorithm run faster, but only by a constant factor. We can say that your culling method weeds out some percentage of the substrings to check. Let's say it weeds out half, just so we have a number to work with. If you match 0.5N substrings, that takes O((0.5N)^2) = O(0.25N^2) = O(N^2) time, and each comparison takes O(N), so it still takes O(N^3), even though it's four times faster than it would be without the culling. What I can do some time is download your code, make some random input strings of different lengths and do experimental complexity analysis of both solutions. I'll post an excel sheet with the results in a couple of days.
I like this discussion. It's interesting.