Function time complexity

Question

I am trying to figure out the time complexity (Big-O) of functions and try to provide an appropriate reason.

First function:

r = 0 # Assignment is constant time. Executed once. O(1) for i in range(n): for j in range(i+1,n): for k in range(i,j): r += 1 # Assignment and access are O(1). Executed n^3 

like this.

I see that this is a triple nested loop, so it should be O (n ^ 3). but I think that my reasoning here is very weak. I really don’t understand what is going on inside inside a triple nested loop here

Second function:

 i = n # Assignment is constant time. Executed once. O(1) while i>0: k = 2 + 2 i = i // 2 # i is reduced by the equation above per iteration. # so the assignment and access which are O(1) is executed # log n times ?? 

I found that this algorithm is O (1). But, like the first function, I do not see what happens in the while loop.

Can someone explain in detail about the time complexity of the two functions? Thanks!

Answer 1

In such a simple case, you can find the number of iterations of the inner loop itself as a function of n exactly :

 sum_(i=0)^(n-1)(sum_(j=i+1)^(n-1)(sum_(k=i)^(j-1) 1)) = 1/6 n (n^2-1) 

those. Θ(n**3) time complexity ( see Big Theta ): it is assumed that r += 1 is O (1) if r has O(log n) digits (the model has words with log n bits ).

The second cycle is even simpler: i //= 2 - i >>= 1 . n has Θ(log n) digits, and each iteration falls on one binary digit (shift to the right), and therefore the whole cycle Θ(log n) , if we assume that the shift i >> 1 log(n) digits is an operation O (1) (the same model as in the first example).

Answer 2

Well, firstly, for the first function, the time complexity seems closer to O (N log N), since the parameters of each cycle decrease each time.

In addition, for the second function, the runtime is O (log2 N). Except, say, I == n == 2. After one run, I am 1. After another, I am 0.5. After the other, I am 0.25. And so on ... I assume you need int (i).

For a rigorous mathematical approach to each function, you can go to https://www.coursera.org/course/algo . This is a great course for this kind of thing. In my calculations, I was sloppy.