The title says it all. I'm going to be parsing a very large JSON string and was curious what the complexity of this built in method was.

I would hope that it's θ(n) where n is the number of characters in the string since it can determine whether there is a syntax error or not.

I tried searching but couldn't come up with anything.

The title says it all. I'm going to be parsing a very large JSON string and was curious what the complexity of this built in method was.

I would hope that it's θ(n) where n is the number of characters in the string since it can determine whether there is a syntax error or not.

I tried searching but couldn't come up with anything.

• javascript
• json
• time-complexity

• Note that could be a good question on the Computer Science board... cs.stackexchange.com – Alexis Wilke Commented Nov 3, 2014 at 5:34
• I don't think there's no real possibility of ambiguity when parsing JSON; after each character is consumed, we know exactly what the current structure is (starts an array or object, starts or continues a primitive, is a property name or an object property value after colon, etc., etc.), or we know with complete certainty that there is a parse error, I don't see how the time-complexity could be higher than n. I'm not an expert in parse theory or complexity theory, though. (Memory complexity might be said to be dependant on the depth of the structure, perhaps? Again, not a complexity expert.) – apsillers Commented Nov 3, 2014 at 5:39

3 Answers 3

JSON is very simple grammar that does not require even lookaheads. As soon as GC is not involved then it is purely O(n).

I do not know of the implementations in browsers, but your assumption is correct to a certain point. If the JSON includes mainly strings, it will be straight forward and very linear. If you have many floating points, it will take a bit of time to convert the numbers, but again quite linear (numbers with more digits take slightly longer, but in comparison to a long string... very similar).

Since in most cases arrays and objects are declared as maps, the memory allocation grows as required and will generally be linear. Many (if not most) implementations will make use of Java as a backend. This means garbage collection and thus a quite impossible way to know for sure how much time will be required to transform all the data as it will very much depend on things such as the size of the memory model used on the target computer and how often the garbage collection runs. However, it should generally just grow as items are added to the map and it will thus mostly look like it is linear as well. I would not expect an implementation to make use of a realloc() which would mean copying data and thus being slower and slower as an array/object grows bigger and bigger.

Was curious a little more so to add more info I believe this is the "high-level" implementation of JSON.parse. I tried finding if Chromium has their own source for it and not sure if this is it? This is going off of the source from Github.

Things to note:

• worst case is probably the scenario of handling objects which requires O(N) time where N is the number of characters.
• in the case a reviver function is passed, it has to rewalk the entire object after it's created but that only happens once so it's fairly negligible. Also depends what the reviver function is doing and you will have to account for it's own time complexity.