平均時間計算量の求め方がわからない

int compare(int *d1, int *d2, int n)
{
	for(int i = 0; i < n; i++){
		if(d1[i] != d2[i]){
			return 0;
		}
	}
	return 1;
}

 なんでこれの平均時間計算量が、1回あたりO(n)になるんだ???
 ループは最低1回で終了するし、最大でn回ループするんだから、O(n/2)じゃないの?
 計算量の求め方がチンプンカンプン。基礎の基礎から勉強できる本とかないもんかなぁ。