Big O notation for .forEach with .find

What is the big O notation for the following code?

    _data.validatorInfo.result.validators.forEach((_validator) => {
        let del = {
            delegation: _data.delegations.result.delegation_responses.find(
                res => res.delegation.validator_address === _validator.operator_address
            ),
            validator: _validator,
            rewards: _data.totalRewards.result.rewards.find(
                re => re.validator_address === _validator.operator_address
            )
        }
        result.delegations.push(del);
    })

Since it has a .forEach and two .find() operations nested, can I assume it is O(N^3)?

You go through all validators (V), for each of them going through delegation_responses (P) and rewards (W) until a certain element is found, which on average means to go through half of the array .

This would give you V * (P + W)/2. Big O ignores constants factors (sets them to 1), so that gives you O(V * (P + W)). And at that point, you can start arguing:

• If P and W are very small compared to V (like orders of magnitude), you would argue that they behave like constants and only slightly scale the driving factor V, and you deal with effectively linear complexity O(N), where N is the number of validators.

• If V is very small (again, orders of magnitude) compared to P and/or W, you would get O(N) or O(N + M), where N and M are number of responses/rewards, again arguing that V behaves like a constant.

• If they are all about the same size (or you cannot make assumptions about their size), you get O(N * 2N), which is O(N²).

Your complexity is

O(N*(M+Q)), where

• N is _data.validatorInfo.result.validators.length
• M is _data.delegations.result.delegation_responses.length and
• Q is _data.totalRewards.result.rewards.length

You can assume that this

• is quadric if N ~ M+Q
• linear if N >> M + Q

Rather than answering your question directly, I want to point out that performance can be improved very easily. A common way to do this would be to use a hash table (Object or Map) to find the items you're looking for.

const delegations = new Map();
_data.delegations.result.delegation_responses.forEach((res) => {
  delegations.set(res.delegation.validator_address, res);
});

const rewards = new Map();
_data.totalRewards.result.rewards.forEach((re) => {
  rewards.set(re.validator_address, re);
});

_data.validatorInfo.result.validators.forEach((_validator) => {
  result.delegations.push({
    delegation: delegations.get(_validator.operator_address),
    validator: _validator,
    rewards: rewards.get(_validator.operator_address),
  });
});

Using the same letters as the answer of Radu Diță

> - N is _data.validatorInfo.result.validators.length
> - M is _data.delegations.result.delegation_responses.length and
> - Q is _data.totalRewards.result.rewards.length

This improved version would result in complexity O(N+M+Q).

You might be able to use

result.delegations = _data.validatorInfo.result.validators.map(...);

if your scenario allows for it.