0

Can anyone help me to calculate and explain me time complexity of this algorithm :

function mystery(n)
    r := 0
    for i := 1 to n − 1 do 
        for j := i + 1 to n do 
            for k := 1 to j do
                r := r + 1 
    return(r)
Michu93
  • 5,058
  • 7
  • 47
  • 80
TungVuDuc
  • 19
  • 1
  • 6
  • Is `return(r)` supposed to be outside the loops? If so please fix your indentation. – k_ssb May 13 '18 at 09:25
  • Have you attempted the problem? Usually people are more willing to help if you can explain your attempt. – k_ssb May 13 '18 at 09:30
  • The return value of the function gives the complexity. It is not hard to prove that the function returns *n³/3 - n/3*, and thus it is *O(n³)*. – trincot May 13 '18 at 11:14

1 Answers1

1

I have no idea how to make sigma character on StackOverflow but it will be:

Sigma(i=1; n-1)Sigma(j=i+1; n)Sigma(k=1;j)1=Sigma(i=1; n-1)Sigma(j=i+1;n)j

you can simplify the inner Sigma by:

Sigma(j=i+1; n)j = Sigma(j=1;n)j - Sigma(j=1;i)j = n(n-1)/2 - i(i-1)/2=n^2-i^2+n-i

then you have:

Sigma(i=1; n-1)n^2-i^2+n-i

It will be O(n^3) but get my answer more as a tip than solution

Michu93
  • 5,058
  • 7
  • 47
  • 80
  • `Sigma(i=1; n)=n(n+1)/2` Where does this come from? – k_ssb May 13 '18 at 09:46
  • 1+2+3+...+n = n(n+1)/2 I would prove it by induction – Michu93 May 13 '18 at 09:47
  • 1
    Yes but that would be `Sigma(i=1; n) i`, but you don't have a sum over `i`. – k_ssb May 13 '18 at 09:49
  • Oh, typo, sorrry, I'm editing – Michu93 May 13 '18 at 09:49
  • I don't think you understand what I'm trying to point out. Where in the original problem did you get a sum over `i`? – k_ssb May 13 '18 at 09:51
  • Well, I just presented this this formula to let @TungVuDuc know where did it come from. It's really unconfortable to write pure math on StackOverflow btw – Michu93 May 13 '18 at 09:53
  • I know how to solve this problem, but I can't understand your answer. That makes me think your answer is very confusing. The expression `Sigma(i=1; n)i=n(n+1)/2` has no logical connection to the rest of your answer, so I don't know why it's there. – k_ssb May 13 '18 at 09:56
  • I don't understand the line `Sigma(j=i+1; n)j = (n+i+1)(n-1)/2` – TungVuDuc May 13 '18 at 10:03
  • Do you think it's more clear now? @pkpnd I just wrote this formula to let op know what I used to count inner Sigma. Probably it wasn't clear. – Michu93 May 13 '18 at 10:12
  • @Michu93 Your answer now makes more logical sense, thanks. – k_ssb May 13 '18 at 10:17