maths.free › Discrete Math & Logic › Algorithms and growth of functions

Algorithms and growth of functions

Big-O notation, comparing growth rates, and what "efficient" means.

Big-O compares functions by eventual growth: n² is O(n³), 2ⁿ dominates every polynomial, n! dominates 2ⁿ. Picture it: the graphs of n, n log n, n², 2ⁿ pulling apart. Think it: P vs NP asks whether a whole class of problems is polynomial, the Frontiers page.

Ví dụ đã làm · limit of (2^n)/(n!) as n -> oo

Calculus · Limits

Limit of 2^n/factorial(n) as n → oo

\lim_{n \to \infty} \frac{2^{n}}{n!}

Bước một bước

  1. \lim_{n \to \infty^+-} \frac{2^{n}}{n!}

    Try direct substitution first.

  2. \

    As x grows without bound, compare the fastest-growing terms (or divide top and bottom by the highest power).

  3. = 0

    Take the limit.

Giải đáp
0

Now you Chọn một bài toán, hoặc gõ hoặc vẽ của riêng mình. Mỗi bước, một bức tranh, câu trả lời ẩn cho đến khi bạn hỏi.

Để cho anh làm việc

Một tài khoản miễn phí thêm ghi chú vào mỗi bài học, ghi chép những gì bạn đã hoàn thành, các bài toán bạn giải quyết ở một nơi, và một giáo viên bạn có thể hỏi về trang này. Toán học là mở cho mọi người, dù có đăng nhập hay không.

Đăng ký Đăng nhập

Ký hiệu được dùng ở đây

Nhấn vào bất kỳ ký hiệu nào để xem định nghĩa đầy đủ, một bức ảnh, và ý nghĩa của từng chữ cái trong nó.

Làm thế nào: Algorithms and growth of functions

  1. Try direct substitution first.
  2. As x grows without bound, compare the fastest-growing terms (or divide top and bottom by the highest power).
  3. Take the limit.

Câu hỏi người ta hỏi

What makes mathematics "discrete"?

It deals with separate, countable objects (integers, graphs, statements) rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

What order should I take these lessons in?

Logic and proof first, because every later lesson proves things. Then induction, sets, relations and functions, counting, recurrences, graphs, Boolean algebra and automata, and finally algorithms and complexity, which use nearly everything before them.

Is discrete mathematics the same as the maths of computer science?

Largely. Data structures are graphs and trees, correctness arguments are induction, running times are recurrences and sums, circuits are Boolean algebra, and what a computer can do efficiently is the subject of the last lessons. It is also ordinary mathematics in its own right.

Do I need calculus for this course?

No. School algebra is enough. A little familiarity with limits helps when comparing growth rates, and the lesson on asymptotic analysis explains the one limit fact it uses.

More in Discrete Math & Logic

Truth tablesSums and inductionProof by inductionPredicate logic and quantifiersDirect proof, contrapositive and contradictionStrong induction and the well-ordering principleRelations: equivalence relations and partial ordersFunctions and cardinalityCounting: rules, choices and bijectionsThe pigeonhole principleSolving linear recurrence relationsGraphs: degrees, paths and connectivityTrees and spanning treesEuler and Hamilton paths