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.

工作范例 · 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!}

一步

\lim_{n \to \infty^+-} \frac{2^{n}}{n!}
Try direct substitution first.
\
As x grows without bound, compare the fastest-growing terms (or divide top and bottom by the highest power).
= 0
Take the limit.

发送答案

现在轮到你选择问题, 输入或绘制您自己的。每一步, 图片, 答案隐藏到您询问。

保持你自己的工作

免费账户在每一课上都添加注解, 记录你完成的, 在一个地方解决的, 以及您可以询问的关于此页的导师。数学本身向每个人开放, 是否签名。

签名上签名登录

此处所用符号

输入完整定义、图片和其中每个字母的含义的符号。

如何: Algorithms and growth of functions

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

人们对人们提出的问题

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.