Back and forth

Computer Science Level 1

count=0
for i in range(0,n):
   for j in range(i,0,-1):
        count=count+1

What is the time complexity of the above code snippet shown above?

O(n)

O(n^{2})

O(n\log n)

O(n^{2}\log n)

1 solution

Christopher Boo
May 15, 2016

For each $i$ in the first for loop, the second for loop will run count = count + 1 $i$ times. Since $i$ ranges from $0$ to $n$ . The number of iterations are

$1+2+ \dots + n = \frac{n(n+1)}{2} \rightarrow O(n^2)$

Rule of thumb : take only the one with the highest power, since they contribute more to the runtime, and remove any constants and coefficients.

Back and forth

1 solution

0 pending reports