Time Complexity Affected by Other Methods?

General Questions
#1

Hello,
I’m new to the USACO forum, it looks really nice. I love the USACO guide, it’s really great. I had a question about time complexity. If you use a method that would take at least one loop to do (like the sort method), then does it affect the time complexity?

For example:

For loop through a list of n elements
for loop through a list of n elements again
n.sort()

Would this have a time complexity of O(N^2) or O(N^3) (because of the sort through N)?

Thanks,
~Zanderman

#2

The complexity would actually be O(n^3\log n), because the complexity of the sorting algorithm is O(n\log n). Not sure why you would want to sort the same thing so many times though.

#3

Ah thanks. Note it was just an example; I was wondering in general if it would be true.

2 Likes