Complexity of a jQuery Expression

Question

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

Instead of asking about the complexity of a 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: A correct answer to this will demonstrate both an understanding of basic computer science principles as well as a deeper knowledge of what jQuery is doing behind the scenes.

So, what is the correct answer?

(I would actually find it easier to talk about the complexity (Big O) of a merge sort, even though it's been a while since I've done any real analysis of algorithms. Not since college!)

Answer 1

Here it is, line by line:

("#nav a") - finding matched elements is O(N) task in general. Consider that #nav is assigned to the body element and all you have in your document are <a>s. You need to scan all of them against "a" selector.

.addClass("link") - that's O(n) task for just to walk through the list. But it has hidden cost - by changing class of element you are asking browser to recalculate style of the element and all its descendants. So in worst case all DOM elements will be affected. Considering that cost of style recalculation is O(N*S) task (N - number of DOM elements, S - number of style rules in all style sheets) then total price will be O(N*S)

.attr("data-initialized", true) - that in principle has the same price as above.

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

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

UAs usually do some optimizations but worst case mandated by CSS selector structure is like that.

Update: for the brevity "small" things like creation of DOM attribute nodes for "data-initialized" for example are left out.