What's the complexity of getJSONObject and getJSONArray methods?

Question

I'm using org.json library as JSON-client for my Java application and I would like to know the complexity of some methods from this lib.

I'm retrieving thousands of JSON objects inside a JSON array inside another JSON objects (and so on) from a database via it's HTTP API. As an example (and only as an example, my case is much more complex), suppose that I'm doing something like that:

// Ignoring attributes types
import org.json.*;

public static void main(String[] args) {
    response = MyHTTPClient.post(url, query).asJSON();
    response = JSON.parse(response);
    data = response.getJSONObject(1).getJSONArray("results").getJSONObject(0);
}

What's the complexity of getJSONObject(int) and getJSONArray(String) methods from org.json library? Is it running in a constant [O(1)] or linear [O(n)] time? If none, what's the correct answer?

Answer 1

org.json will parse the entire JSON document when you instantiate the JSONObject from a string (or JSONTokener). The getJSONObject() and getJSONArray() methods are just typed versions of the untyped get() methods (which return Object instance). if you look at the source you can see that JSONObject uses a HashMap while JSONArray uses an ArrayList for internal representations, so the execution times are close-to-constant (O(1))