1
def x(lst):
   z = 0
   for a in range(len(lst)):
       for b in range(len(lst)):
           mx = lst[0][0]
           if mx > z:
               z = mx           
   return z.

I'm trying to find the complexity Big O of the function. So with the nested list, it would be O(n^2), but it also had a condition statement that would go through all the elements in the list, so would it it be O(n^3) ?

Nonhey1
  • 27
  • 3
  • Nobody can tell you the complexity of a function if there is some code missing. For example, if the first `some code` is `break` then the complexity is O(n). If it's `return` its O(1), etc. We can give you any answer depending on how we fill the gaps. – cglacet May 08 '20 at 02:20
  • `if (something that's O(1))` is O(1) so doing an O(1) operation O(n^2) times is still O(n^2) – apokryfos May 09 '20 at 08:00

2 Answers2

2

If some code in the condition goes through all the elements of the list, and the number of times that some code runs is proportional to the number of elements in lst, then the time complexity would be O(n3).

If the number of times that the condition evaluates to true is not proportional to len(lst), then the time complexity would be lower. For example, if the number of times that some code runs is constant regardless of the size of the list, then the time complexity would only be O(n2).

Daniel Giger
  • 2,023
  • 21
  • 20
  • the number of times that `some code ` runs is proportional to the number of elements in lst, it goes through all the elements of the list first, so i guess the complexity is O(n^3). Thank you – Nonhey1 May 08 '20 at 02:59
  • @Nonhey1 In your updated version, the code inside the if statement doesn't go through all the elements in the list, so your updated version is O(n^2). – Daniel Giger May 08 '20 at 03:24
0

Your code is obviously mistaken but time complexity is no doubt O(n^2)

Harsh Prakash Agarwal
  • 295
  • 3
  • 10
  • yeah sorry about that..... But thank you for your answer. On that note, do you also know the complexity of the sqrt function ? – Nonhey1 May 09 '20 at 08:07
  • @Nonhey1 if I recall correctly there's an algorithm that can calculate the square root in time proportional to the number of digits of the number. If you are using 32 bit or 64 bit numbers then that's effectively O(1) (since the length is constant) – apokryfos May 09 '20 at 08:41