-1

I need help understanding how to breakdown this function so I can know how to get to the answer of the questions being asked? I know the order of growth but still have some doubts about how to read this on an algorithm?

What is the big O complexity of the following function?

def complexity(n):
  k = 0
  for i in range(2, n):
    for j in range(n, 2*n):
      k= k+1
  • (a) complexity1: O(n3)
  • (b) complexity1: O(n2)
  • (c) complexity1: O(n)
  • (d) complexity1: O(nlogn)
  • (e) None of the above
Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
LeoT2020
  • 1
  • 1
  • 1
    Welcome to SO! If you paste code into your question, please make sure that it's properly formatted. It's unreadable at the moment. Furthermore, please make an effort to solve this homework yourself. This exercise is so simple that you should be able to do it yourself if you have looked at a couple of examples. – Mo B. Dec 09 '20 at 10:55
  • Read this carefully and attempt to solve the question yourself after that: https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it?rq=1 – Mo B. Dec 09 '20 at 11:28

1 Answers1

0

If you consider the summation

enter image description here

you can see that the number of steps performed are exactly (n-2)*n.
Thus, the time complexity T(n) = O(n^2).

Practical example:

>>> complexity(5)
15
>>> complexity(10)
80
>>> complexity(20)
360
abc
  • 11,579
  • 2
  • 26
  • 51