I'm wondering, when JavaScript compares 2 objects, does it have to iterate through each key recursively to determine strict equality (O(log(2n))? If you compare strings in JavaScript, does it have to compare them by each letter or can the sum of the binary information be enough for a 1 to 1 comparison O(1)? Is it faster to compare JSON objects, or javascript objects?
Any answers to any part are appreciated or corrections to my primitive combinatorics.
In JS, objects are compared by references (not structural/deep equality). Because only a fixed-length memory address is being compared, the comparison is O(1).
For example, the below code snippet always prints false even though every key/value pair across obj1 and obj2 are the same. obj1 and obj2 do not refer to the same underlying object, and objects are compared by reference, not keys and values.
let obj1 = { a: 1, b: 2 };
let obj2 = { a: 1, b: 2 };
console.log(obj1 == obj2 || obj1 === obj2); // => falseThis code, however, prints true, because in this case obj1 and obj2 do refer to the same object.
obj1 = { a: 1, b: 2 };
obj2 = obj1;
console.log(obj1 == obj2 && obj1 === obj2); // => trueIf you want to compare the structure and contents of two objects rather than just assessing referential equality, you could use Node's assert.deepEqual(), which is linear in the total number of key/value pairs to be compared.
To compare arbitrary objects in the browser, you could use JSON.stringify(obj1) === JSON.stringify(obj2). This is also roughly linear in the number of key/value pairs being compared, but it depends on the length of the stringified versions of the key/value pairs rather than just the number of key/value pairs. You could say it's O(nm), where n is the number of k/v pairs, and m is the average string length of the k/v pairs in the object, such that nm is the total length of the string JSON.stringify produces. (m might just be a small constant, but without prior knowledge bounding it, it could very well exceed n, so you have to factor it in)
Generally, assert.deepEqual() can be faster in the best case because it can return earlier: as soon as a key/value pair being compared does not match, the assertion can fail and return early. If the first k/v pairs don't match, assert.deepEqual() could return in O(1). However, in the worst case, comparing equal objects, it is O(n).
With JSON.stringify, the entire objects have to be converted to strings before the comparison begins, so it is O(nm) best and worst case. You could of course also implement your own, recursive deepEquals method to achieve the same performance as assert.deepEqual(), or use lodash.isEqual(), they're just not native.
Addressing your other question, strings can't be compared in O(1) by "the sum of their binary information". Two different strings could sum to the same value, and determining that sum would nevertheless be linear in the number of bits in the binary representations. The number of bits in a length n string's binary rep is O(n) because every character is represented by fixed number of bits. If instead you mean to compare the strings bit by bit (which is essentially what happens in a standard string comparison), that's still O(n) for the same reason.
I think you might be conflating the O(1) comparison complexity of fixed size integers with the complexity for string comparisons. The relevant difference is that integers can be compared in O(1) when they're stored in single machine-words of memory (eg comparing two <= 64 bit integers on a 64 bit machine), but strings are generally stored character by character, with the entire string value likely not fitting into a single memory address. The only time string comparison would always be O(1) in JS is if the strings had previously been interned, but this wouldn't help you with comparing JSON.stringified objects because you'd still need to do the two O(nm) stringifications up front.
