Pascal-komplexitet

Hur många par blir det? 

Laguna skrev:

Hur många par blir det? 

Blir antalet bearbetningssteg  $\frac{n(n+1)}{2}$?

Frågan är egentligen lite wonky eftersom en algoritm som gör detta kan vara sämre än O(n^2). En algoritm kan trots allt inte definieras av vad den producerar (listan) utan endast hur den gör detta.

Men om man tar det på allvar att det tar "ett bearbetningsteg att ta fram" ett element så blir komplexiteten samma som antalet sådana oordnade par dvs

$O(n(n + 1)/2) = O(n^2/2 + n/2) = O(n^2/2) = O(n^2)$ 

såsom du antagit. 

SeriousCephalopod skrev:

Frågan är egentligen lite wonky eftersom en algoritm som gör detta kan vara sämre än O(n^2). En algoritm kan trots allt inte definieras av vad den producerar (listan) utan endast hur den gör detta.

Men om man tar det på allvar att det tar "ett bearbetningsteg att ta fram" ett element så blir komplexiteten samma som antalet sådana oordnade par dvs

$O(n(n + 1)/2) = O(n^2/2 + n/2) = O(n^2/2) = O(n^2)$ 

såsom du antagit. 

Ja, då fattar jag vad de menade med uppgiften. Tack!