Giả sử f(n) = akn^k + ak-1n^k-1+....a1n +a0. Chứng minh rằng f(n) = O(n^k)

Giải SBT Tin học 11 Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Câu 25.7 trang 78 SBT Tin học 11: Giả sử f(n) = a_kn^k + a_k-1n^k-1+....a₁n +a₀. Chứng minh rằng f(n) = O(n^k).

Lời giải:

Theo Quy tắc 1, ta có O(f(n)) = O(a_kn^k + a_k-1n^k-1+....a₁n +a₀)= O (n^k)

Vậy suy ra f(n) = O(n^k)