Description
This check iterates over the list existing_relationships
up to 2 times:
tools-python/src/spdx_tools/spdx/parser/jsonlikedict/relationship_parser.py
Lines 162 to 172 in 8050fd9
And it's called for every file:
tools-python/src/spdx_tools/spdx/parser/jsonlikedict/relationship_parser.py
Lines 144 to 157 in 8050fd9
So if F
is the number of files and R
is the number of relationships, we are doing O(F * R)
comparisons of relationships (which seem not cheap individually).
And given that this seems to expect to find a relationship for every file, we know that R is >= F
, so this is at least O(F^2)
.
Looks quadratic to me.
With the caveat that I'm not a python expert, this being a list seems to be the issue:
Is it possible to turn that into a set so these membership tests are O(1) instead of O(N)?