n位二進制數加一的時間複雜度

這是資料結構老師布置的第二道作業題，題目要求如下：

下列算法完成對一個n位二進制數加1的操作（假如無溢出）。顯然，該算法在最壞情況下的時間複雜度為O(n)，試問平均情況下的時間複雜度是什麼？請用數學推導或實驗驗證的方式證明你的結論。

void Inc(int A[]) {
  int i;
  i=n-1;
  while (A[i]==1) 
     { A[i]=0; i--; }
  A[i]=1;
}
           

解答：

算法在最好情況下，即二進制數的最後一位為零時，隻進行一次判斷，未進行循環體，指派語句也執行了一次，最壞情況即題目假設情況，指派語句執行n-1次，算法複雜度為O(n)，循環體平均執行0.5n次，是以平均時間複雜度為O(n)。