Quando si prendono in considerazioni le complessità degli algoritmi, si devono utilizzare funzioni matematiche, come p. es. n, n^2, log(n)... Non puoi dire, per esempio, quale sia la complessità di un programma che entra in un loop infinito: semplicemente il programma non funziona. O se, ancora un altro esempio, la memoria va in overflow, sicuramente windows ti avvisa e blocca tutto, ma questo è indipendente dalla complessità dell'algoritmo che hai usato.
E in ogni caso la complessità di un programma non può certo dipendere dal sistema operativo sotto il quale lo fai girare.