I'm farily new to time complexity. I'm looking for the time complexity of this code
def func(arg): list= [] for i in range(len(arg): list.append(arg.count(i) return list I know that the loop would make it O(n), but then count is also O(n) in python, would that make this function O(n) or O(n2)?
You have a loop within a loop:
for i in range(len(arg)): # outer loop => O(n) arg.count(i) # inner loop hidden inside a function => O(n) So that's O(n^2).
If you wanted two loops that sum to O(n), you'd need something like this:
for x in range(N): # O(N) ... # do stuff for y in range(N): # O(N) ... # do other stuff The overall complexity will be the sum of the loops' complexities, so
O(N) + O(N) = O(2 * N) ~= O(N) O(n^2). The outer loop executes n times the inner statement(which is O(n)) so we get quadratic complexity.
