Notacja O(n) oraz szacowanie złożoności czasowej z rozmiaru danych

Siemka,
zaczynam naukę algorytmiki do OI. Mam problem ze zrozumieniem szacowania złożoności czasowej algorytmu na podstawie rozmiaru danych. Chodzi o to, że dla danego rozmiaru (zazwyczaj limit to 32MB, 64MB, 128MB lub 256MB) możemy spodziewać się rozwiązania w takiej złożoności, aby to rozwiązanie było najszybsze ?

Ale co ma piernik do wiatraka? Ilość dostępnej pamieci nijak sie ma do złożoności obliczeniowej algorytmu. Złożoność liczy sie ręcznie na bazie algorytmu.

zaczynam naukę algorytmiki do OI. Mam problem ze zrozumieniem szacowania złożoności czasowej algorytmu na podstawie rozmiaru danych. Chodzi o to, że dla danego rozmiaru (zazwyczaj limit to 32MB, 64MB, 128MB lub 256MB) możemy spodziewać się rozwiązania w takiej złożoności, aby to rozwiązanie było najszybsze ?

Jeśli dobrze rozumiem pytanie, to chodzi Ci o szacowanie złożonosci obliczeniowej ( O(n) ) z n. n nie ma nic wspólnego z rozmiarem danych w megabajtach, a jest zwykłym skalarem (np. na wejściu jest 10000 liczb więc n=10000).

Bardzo przybliżone szacowanie dobrej złożoności algorytmu do zadania: przyjmij jakąś sensowną stałą ilość operacji którą program jest w stanie wykonać w danym czasie (np. 10^9 operacji).

Wtedy:
Algorytm O(n) poradzi sobie z n <= 1000000000
Algorytm O(n log n) poradzi sobie z n <= 39620078
Algorytm O(n^2) poradzi sobie z n <= 31622
Algorytm O(n^3) poradzi sobie z n <= 1000
Algorytm O(n^4) poradzi sobie z n <= 177
Algorytm O(2^n) poradzi sobie z n <= 29
Algorytm O(n!) poradzi sobie z n <= 12

Więc w drugą stronę, jeśli masz n powiedzmy 30000, możesz się spodziewać że dasz radę się zmieścić w czasie z algorytmem O(n^2), ale O(n^3) już nie.