JQuery expression complexity

Question

I read this article - http://css-tricks.com/interviewing-front-end-engineer-san-francisco - about interviewing a front engineer. The guy who wrote the article suggested the following:

Instead of asking about the complexity of merge sort, ask about the complexity of this jQuery expression:

$("#nav a") .addClass("link") .attr("data-initialized", true) .on("click", doSomething) 

He goes on to say: the correct answer to this will demonstrate both an understanding of the basic principles of computer science and a deeper knowledge of what jQuery does behind the scenes.

So what is the correct answer?

(It would be easier for me to talk about the complexity of (Big O) merge sorting, although it was a long time ago since I did some real analysis of the algorithms. Not starting in college!)

Answer 1

Here it is, line by line:

("#nav a") - finding matching elements - this is the O(N) task as a whole. Note that #nav is assigned to the body element, and all you have in the document is <a> s. You need to scan them all against the "a" selector.

.addClass("link") - this O(N) task is just for going through the list. But it has a hidden cost - by changing the class of the element that you request from the browser, recount the style of the element and all its descendants. Therefore, in the worst case, all DOM elements will be affected. Given that the cost of recalculating a style is O(N*S) task ( N is the number of DOM elements, S is the number of style rules in all style sheets), then the total price will be O(N*S)

.attr("data-initialized", true) - this basically has the same price as above.

.on("click", doSomething) - the O(N) task ( N are the numeric elements in the set) + it has the cost of allocating memory for event binding structures. Each element in the set will have a new binding, and therefore additional memory is allocated.

So the general answer is O(N*S) for computational complexity and M(N) for memory consumption.

Usually UAs do some optimization, but the worst case given by the CSS selector structure is like this.

Update: for brevity, “small” things, such as creating DOM attribute nodes for “initialized data,” for example, are not taken into account.