Time complexity of traversing nested JS object

Question

I would like to know in which time complexity I am traversing my nested JS Object. For traversing the JS Object I am using three nested for-loops e.g.

Sketch of the For-Loop:

for(const page in object){
  for(const group in page){
    for(element in elements){
       }
      }
    }

I need to visit every element of each elements for each group a page has.

JS Object:

{
"Page 1":{
    "Group 1": {
        "Elements": [
            "Element 1",
        ]
    },
    "Group 2": {
        "Elements": [
            "Element 1"
        ]
    }
},
"Page 2":{
    "Group 1": {
        "Elements": [
            "Element 1",
            "Element 2"
        ]
    }
}

}

Is it O(n) due to the fact that I am visiting each elements only a single time?

Does this answer your question? Time complexity of nested for-loop — briosheje
– briosheje, Commented Jul 20, 2022 at 11:56
It depends on what n is. If n is the sum of elements inside the Elements arrays, then yes it is O(n) — Keimeno
– Keimeno, Commented Jul 20, 2022 at 11:59
Well, it's O(n) where n is the total number of elements nested into those objects. — AKX
– AKX, Commented Jul 20, 2022 at 11:59
I need to visit every element of elements. But to get there I need to go through every page and every group aswell. So the time complexity will be much higher O(N^3) ? — Contexys
– Contexys, Commented Jul 20, 2022 at 12:01

trincot · Accepted Answer · 2022-07-20 12:16:18Z

1

The complexity is O(P+G+E) where

P stands for the number of pages
G stands for the total number of groups
E stands for the total number of elements.

In practice this is equivalent to O(E), but if you would have empty pages and/or empty groups (so without elements), then either P or G could be greater than E, and then it is important to speak of O(P+G+E).

If however it is guaranteed that every page has at least one group, and every group has at least one element, then E is the greatest among (P, G, E), and so O(P+G+E) = O(E).

answered Jul 20, 2022 at 12:16

trincot

357k38 gold badges282 silver badges339 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time complexity of traversing nested JS object

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related