I'm not sure if this is O(n log n) as mentioned in the comments, but I used a hashing algorithm instead of my original naive nested for loop originally posted in comments. Basically, you compute the minimum of the 2 string lengths, as an optimization / exclude impossible solutions. Then you work ...
No offense but I think you're wrong. pastebin.com/Q3Sd69N5 Run that code in your console, and please explain to me why there is a gigantic difference between my calculated ops and n^3? FYI it turns out to be O(n^2) in the worst case not O(n^3). Notice how I didn't nest those for loops?
Your link only addressed its complexity relative to the number of elements in a data structure. The length of each element is something else. So, for example, the complexity of most operations in a normal BBST implementation (such as red-black tree) is in fact O(m*log(n)), where n is the number of elements in the BBST as that page states, and m is the time comparing two elements (or in case of hash or trie, the time processing each element), which is just the length for a string. And for hash tables, n doesn't contribute to the complexity and it's O(m).
So you're basically adding the Big O for the hashing function of each string? I don't know, something seems odd about that. Then, what about my calls to .substring? should we count that too in the Big O, assuming very naively that the internals is doing a for loop from start to end index? I'll just agree to disagree, given that
For substring, I don't know. Many implementations are indeed O(n), but there are ways to implement it in O(1). But for a hash table, it cannot be implemented in a lower time complexity.
Just as an example, given a whatever data structure supporting add and has, you only add one string a and then find another string b in it. This is equivalent to simply comparing whether a and b are equal. Do you think this can be done in O(1) when the two strings are long?
Well, lets say I have 2 very long strings, assume equal length. The strings could be the same except for the last character, or they could be different at that first character. Assuming the first case, that will be basically O(n) and the second case will basically be O(1) because only 1 check is needed
A program checks whether the two strings are equal and do everything slowly in all other cases can also run in O(n) time for the best case for this question, which doesn't make much sense. In your algorithm, if the length of the answer is n/2 and appears at the beginning of the strings, you can always get at least n/4 pairs of strings (if there is no duplicates) from A and B with the first n/4 characters matches, for every length between n/2 and 3n/4. And that's enough for O(n^3).
I'll leave you with this, because I believe we are disagreeing about what constitutes a level of complexity when calculating Big O. : pastebin.com/MrjkYKpF If you think that should be O(n^3), then we will just continue to disagree. Otherwise, I must have missed your point somewhere
All algorithms ending in finite time are O(1) if the input is fixed. It doesn't make sense to speak of the time complexity without explicit input and the definition of n. Assume strings is the input, that's O(m^2k) where m is the length of the list, and k is the length of each string. In the similar routines in this answer, both m and k are O(n) (in average) where n is the length of A and B. But in your link, it is usually just said to be O(m^2k). Using the conventions in theoretical computer science, where mk=O(n), it is O(n^2). Or if you assume k is constant, then it is O(m^2).
Alright, I see where youre coming from so no problem there
just thought of something and I'm very curious on your thoughts now. Would you say this complexity is O(n^3), given the very strict assumptions specified? pastebin.com/DaAvjmtY
Ok. What if we now said the length of the string was m, and the length of the array was n. Assume m is < n. Would the complexity then become O(n^2 * m) ?
I learned 2 things from this. 1) When wikipedia says Linear Search is O(n), it is not O(n) for strings. And 2) Strings can be slower to compare than other types because of their "equals" implementation. Good things to know
Discussion on answer by applejacks01:…
Discussion on answer by applejacks01:…