public boolean equal(MyLinkedList a, MyLinkedList b) {String instanceA = encode(a);String instanceB = encode(b);return instanceA.equals(instanceB);}I was working on a project and looked at my code and realized I didn't know the time complexity rules of calling methods.
What would be the big-O notation of my equal method if the encode(String value) is of O(n)? Would it take into consideration the big-o notation of O(n) or would it be a simple O(1)?
Best Answer
It would be O(n) in the worst case. If you think about it, it boils down to estimating the time complexity of testing for equality, the encodings do not add additional complexity to the problem.
The complexity of verifying that two strings are equal is most of the times < O(n). For example, the equals method could simply compare the length of the strings before actually comparing the contents of the strings, which has constant complexity. If the strings are of equal length, then the equals method could traverse the whole strings, thus O(n).
In CS stackexchange, the subject is discussed in more detail. Check it out here: https://cs.stackexchange.com/questions/127899/what-is-the-expected-time-complexity-of-checking-equality-of-two-arbitrary-strin