And it is O(n^3).

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?

One level for while, one level for for, and one level for hashing. Anyway not O(n).

That's not O(n^3), can you correct your comment?

Use this as a BigO ref when it comes to hashing: bigocheatsheet.com

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

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

@applejacks01 Yeah, that would be O(n^3)

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