Giả sử f(n) = $a_{k}n^{k}+a_{k-1}n^{k-1}+...+a_{1}n+a_{0}$. Chứng minh rằng f(n) = O(n$^{k}$)

Bài 25.7.* Giả sử f(n) = $a_{k}n^{k}+a_{k-1}n^{k-1}+...+a_{1}n+a_{0}$. Chứng minh rằng f(n) = O(n$^{k}$)


Theo Quy tắc 1, ta có O(f(n)) = O($a_{k}n^{k}+a_{k-1}n^{k-1}+...+a_{1}n+a_{0}$))  = O(n$^{k}$).

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


Bình luận

Giải bài tập những môn khác