Có phải O(N^k) sẽ chạy lâu hơn rất nhiều so với O(kN) khi n>>1000 không? (về time complexity)

[yujin2020 (Anna Ngoc)]

Cụ thể hơn là trong 2 thuật toán này:
A(n) = 1024A(n/2) + n^1000
B(n) = 2B(n-1024) + 1

Help me ~~~~!

[rogp10]

Số mũ cỡ đó thì từ n=1 lên 2 đã nhiều lắm rồi ấy hằng số chỉ kéo lại một tí thôi, không ăn thua.

---

Thực ra big-O chỉ nói rằng nếu f(n) = O(g(n)) thì quá một mức nào đó g(n) sẽ ngang hoặc trên f(n). Vấn đề là các hằng số.

Nên so sánh các thuật toán nhân hai số sẽ phù hợp hơn Đánh giá thuật toán đâu chỉ có sắp xếp với tìm kiếm.