> I did mean the Python implementation yes. If this is the case, what the
> runtime complexity for 2 vertices if we use g.vs.find("name")?
Same as a lookup in a Python dictionary. According to the Python wiki, lookups
are O(1) on average in a Python dictionary, although it could be O(n) amortized
worst case (but you shouldn't need to worry about this):https://wiki.python.org/moin/TimeComplexity However, I wouldn't fret about that too much if you are just describing a generic algorithm -- the point is that you _could_ do a name-to-index lookup in O(1) on average if you use a hash table, even if the particular Python dictionary implementation does not use a hash table. So, in your publication, you could simply say that name-to-index lookups can be done in O(1) without mentioning that igraph _happens_ to use a Python dict for this. If I were lazy and did not implement this in the Python interface, it would not make your algorithm any worse, although it would make the _implementation_ of your algorithm worse of course. All the best, Tamas _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
