Question 52426 in Javascript Question posted in
A very good W3school tutorial can be found here.

Big O notation for .forEach with .find – Javascript

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)?

Tags:

3

Answers


  1. 0

    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²).

    Login or Signup to reply.
  2. 0

    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
    Login or Signup to reply.
  3. 0

    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.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search