Quoted By:
Ok the last 2 nested loops are I think you understood that.
I am going to to prove that the total time complexity of the first 3 nested loops is at least (might be less).
We will start from the inner loop. Let us name as the value the var k has in the i'th iteration. We see that and . I cannot work it out as it is but we clearly see that the count of iterations would be more if the transition was (also suppose that k starts at 2 and we ignore the first iteration).
So let's find the number of iterations given the last transition. First of all we notice that .
We will find the biggest i for which .
So for each j we do iterations, let's name the count . So considering the number of iteration of the two final loops
So doing that many iterations N/2 times (first loop) we get that the time complexity is which, equivalently, is written as .
(Again this is the best answer I got but might be incomplete since the real transition of k could make a significant difference).
Sorry for the long post
