[問題] 程式執行次數

[peterpan126 (雲淡風輕)]

    for i <- 1 to n do
       j <- i
      for k <- (j+1) to n do
          x <- x+1
      end
    end

問這程式的執行次數為多少?

我一開始用直覺是認為 n平方 不過第二行有穿插 j <- i，該如何分析呢?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.116.5.37
推 thank1984:外圈i=1 j=1, 內圈k=2 to n 所以執行n-1次 第二圈
→ thank1984:k = 3 to n 執行 n-2次  n-3......1 所以為O(n^2)
→ thank1984:有錯請指正 感謝
推 nowar100:我想的同1樓 O(n)+O(n-1)+...+O(2)+O(1) => O(n^2)
→ nowar100:不過我不確定  還沒念 XD
→ peterpan126:我一開始也是認為是n^2  不過怕有異!
推 thank1984:如果是問次數那就寫 [(n-2+1)*(n-2)]/2