[Solved] Do we really have case in this algorithm [closed]

Question

The comment you wrote in @OBu’s answer is about only a quarter right:
1*n + 2*(n-1) + 3*(n-2) + … +n*1

That equals to:

Sum(i=1..n, i*(n-i+1)) = n*Sum(i) – Sum(i*i) + n = n*[n(n+1)/2] – [n(n+1)(2n+1)/6] + n

If you want, feel free to compute the exact formula, but the overall complexity is O(n^3).

As a rule of thumb (more like a back-of-the-envelope computation trick I’ve picked up… just to give you a quick idea): if you are unsure about algorithms with multiple for’s (with different lengths, but all in relation with n, as you have above) try to compute how many operations are performed around the middle of the algorithm (n/2). This usually gives you an idea on how the running time complexity for the whole thing might looks like – you are basically computing the largest element in the sum, so the overall complexity is always >= than the thing you compute (in most cases it’s the same though).

Accepted Answer

The comment you wrote in @OBu’s answer is about only a quarter right:
1*n + 2*(n-1) + 3*(n-2) + … +n*1

That equals to:

Sum(i=1..n, i*(n-i+1)) = n*Sum(i) – Sum(i*i) + n = n*[n(n+1)/2] – [n(n+1)(2n+1)/6] + n

If you want, feel free to compute the exact formula, but the overall complexity is O(n^3).

As a rule of thumb (more like a back-of-the-envelope computation trick I’ve picked up… just to give you a quick idea): if you are unsure about algorithms with multiple for’s (with different lengths, but all in relation with n, as you have above) try to compute how many operations are performed around the middle of the algorithm (n/2). This usually gives you an idea on how the running time complexity for the whole thing might looks like – you are basically computing the largest element in the sum, so the overall complexity is always >= than the thing you compute (in most cases it’s the same though).