algorithm - “Big O”符号的简单英文解释是什么？

Question

我更喜欢尽可能少的正式定义和简单的数学。

Answer 1

快速说明，我的回答几乎肯定会混淆Big Oh 表示法（这是一个上限）和 Big Theta 表示法“Θ”（这是一个两侧的界限）。但根据我的经验，这实际上是非学术环境中的典型讨论。对造成的任何混乱表示歉意。

---

BigOh 复杂度可以用这个图来可视化：

我可以为 Big Oh 符号给出的最简单的定义是：

Big Oh 表示法是算法复杂性的相对表示。

这句话中有一些重要且故意选择的词：

• 相对：您只能将苹果与苹果进行比较。您无法将进行算术乘法的算法与对整数列表进行排序的算法进行比较。但是比较两种算法来进行算术运算（一个乘法，一个加法）会告诉你一些有意义的事情；
• 表示： BigOh（以最简单的形式）将算法之间的比较简化为单个变量。该变量是根据观察或假设选择的。例如，排序算法通常基于比较操作（比较两个节点以确定它们的相对顺序）进行比较。这假设比较是昂贵的。但是，如果比较便宜但交换很昂贵怎么办？它改变了比较；和
• 复杂性：如果我需要一秒钟来对 10,000 个元素进行排序，那么我需要多长时间才能对 100 万个元素进行排序？在这种情况下，复杂性是对其他事物的相对衡量。

阅读完其余部分后，请返回并重新阅读以上内容。

我能想到的 BigOh 最好的例子就是做算术。取两个数字（123456 和 789012）。我们在学校学到的基本算术运算是：

• 添加;
• 减法；
• 乘法; 和
• 分配。

这些中的每一个都是一个操作或一个问题。解决这些问题的方法称为算法。

加法是最简单的。您将数字排成一行（向右）并将数字添加到一列中，在结果中写入该加法的最后一个数字。该数字的“十”部分被转移到下一列。

让我们假设这些数字的相加是该算法中最昂贵的操作。理所当然地，要将这两个数字相加，我们必须将 6 个数字相加（并且可能带有第 7 个数字）。如果我们将两个 100 位数字相加，我们必须进行 100 次加法。如果我们将两个10,000 位数字相加，我们必须进行 10,000 次加法。

看到图案了吗？复杂度（即操作数）与较大数字中的位数n成正比。我们称之为O(n)或线性复杂度。

减法是类似的（除了你可能需要借而不是进位）。

乘法不同。您将数字排成一行，取底部数字中的第一个数字，然后将其与顶部数字中的每个数字依次相乘，依此类推。因此，要将我们的两个 6 位数字相乘，我们必须进行 36 次乘法。我们可能还需要添加多达 10 或 11 列才能获得最终结果。

如果我们有两个 100 位数字，我们需要进行 10,000 次乘法和 200 次加法。对于两个一百万位数的数字，我们需要进行一万亿（10 ¹²）次乘法和两百万次加法。

由于算法以 n平方进行缩放，因此这是O(n ² )或二次复杂度。现在是介绍另一个重要概念的好时机：

我们只关心复杂性中最重要的部分。

精明的人可能已经意识到我们可以将操作数表示为：n ² + 2n。但正如您从我们的示例中看到的，每个数字都有两个百万位数，第二项 (2n) 变得微不足道（占该阶段总操作的 0.0002%）。

可以注意到，我们在这里假设了最坏的情况。在乘以 6 位数字时，如果其中一个有 4 位，另一个有 6 位，那么我们只有 24 次乘法。尽管如此，我们还是计算了那个“n”的最坏情况，即当两者都是 6 位数字时。因此，Big Oh 表示法是关于算法的最坏情况。

电话簿

我能想到的下一个最好的例子是电话簿，通常称为白页或类似名称，但它因国家而异。但我说的是按姓氏，然后是首字母或名字，可能是地址，然后是电话号码的人。

现在，如果你让计算机在包含 1,000,000 个姓名的电话簿中查找“John Smith”的电话号码，你会怎么做？忽略你可以猜到 S 开始多远的事实（假设你不能），你会怎么做？

一个典型的实现可能是打开中间，取第 500,000^个并将其与“Smith”进行比较。如果它恰好是“史密斯，约翰”，我们真的很幸运。更有可能的是，“John Smith”将出现在该名称之前或之后。如果是在我们之后将电话簿的后半部分分成两半并重复。如果在此之前，我们将电话簿的前半部分分成两半并重复。等等。

这称为二进制搜索，无论您是否意识到，每天都会在编程中使用它。

因此，如果您想在包含一百万个名字的电话簿中找到一个名字，您实际上最多可以通过这样做 20 次来找到任何名字。在比较搜索算法时，我们决定这个比较是我们的“n”。

• 对于 3 个姓名的电话簿，最多需要 2 次比较。
• 对于 7，最多需要 3 个。
• 15个需要4个。
• …</li>
• 1,000,000 需要 20。

这真是太好了，不是吗？

在 BigOh 术语中，这是O(log n)或对数复杂度。现在有问题的对数可能是 ln（以 e 为底）、log ₁₀、log ₂或其他一些底。没关系，它仍然是 O(log n)，就像 O(2n ² ) 和 O(100n ² ) 仍然都是 O(n ² )。

在这一点上值得解释一下，BigOh 可用于通过算法确定三种情况：

• 最佳情况：在电话簿搜索中，最好的情况是我们在一次比较中找到姓名。这是O(1)或恒定复杂度；
• 预期情况：如上所述，这是 O(log n); 和
• 最坏情况：这也是 O(log n)。

通常我们不关心最好的情况。我们对预期和最坏的情况感兴趣。有时其中一个或另一个会更重要。

回到电话簿。

如果您有电话号码并想查找姓名怎么办？警方有一个反向电话簿，但公众拒绝进行此类查找。还是他们？从技术上讲，您可以反向查找普通电话簿中的号码。如何？

您从名字开始并比较数字。如果这是一场比赛，很好，如果不是，你继续下一场。你必须这样做，因为电话簿是无序的（无论如何都是通过电话号码）。

因此，要查找给定电话号码的名称（反向查找）：

• 最佳情况： O(1)；
• 预期情况： O(n)（对于 500,000）；和
• 最坏情况： O(n)（对于 1,000,000）。

旅行推销员

这是计算机科学中一个非常著名的问题，值得一提。在这个问题中，你有 N 个城镇。这些城镇中的每一个都通过一定距离的道路与一个或多个其他城镇相连。旅行推销员问题是找到访问每个城镇的最短路径。

听起来很简单？再想想。

如果您有 3 个城镇 A、B 和 C，所有对之间都有道路，那么您可以去：

• A → B → C
• A → C → B
• B → C → A
• B → A → C
• C → A → B
• C → B → A

嗯，实际上比这要少，因为其中一些是等价的（例如，A → B → C 和 C → B → A 是等价的，因为它们使用相同的道路，只是相反）。

实际上，有3种可能。

• 把它带到 4 个城镇，你就有（iirc）12 种可能性。
• 5是60。
• 6变成360。

这是称为阶乘的数学运算的函数。基本上：

• 5！= 5 × 4 × 3 × 2 × 1 = 120
• 6！= 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7！= 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• …</li>
• 25！= 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000
• …</li>
• 50！= 50 × 49 × … × 2 × 1 = 3.04140932 × 10 ⁶⁴

所以旅行推销员问题的 BigOh 是O(n!)或阶乘或组合复杂度。

当你到达 200 个城镇时，宇宙中已经没有足够的时间来解决传统计算机的问题了。

需要考虑的事情。

多项式时间

我想快速提及的另一点是，任何复杂度为O(n ^a )的算法都被称为具有多项式复杂度或可在多项式时间内求解。

O(n)、O(n ² ) 等都是多项式时间。有些问题不能在多项式时间内解决。正因为如此，世界上使用了某些东西。公钥密码术就是一个很好的例子。在计算上很难找到两个非常大的素数。如果不是，我们就无法使用我们使用的公钥系统。

无论如何，这就是我对 BigOh（修订版）的（希望是简单的英语）解释。

Answer 2

它显示了算法如何根据输入大小进行缩放。

O(n ² ) : 称为二次复杂度

• 1 项：1 次操作
• 10 项：100 次操作
• 100 项：10,000 次操作

请注意，项目的数量增加了 10 倍，但时间增加了 10 ²倍。基本上，n=10 等 O(n ² ) 为我们提供了比例因子 n ²，即 10 ²。

O(n)：称为线性复杂度

• 1 项：1 秒
• 10 项：10 秒
• 100 项：100 秒

这次项目的数量增加了 10 倍，时间也是如此。n=10，因此 O(n) 的比例因子为 10。

O(1)：称为常数复杂度

• 1 项：1 次操作
• 10 项：1 次操作
• 100 项：1 次操作

项目的数量仍然增加了 10 倍，但 O(1) 的比例因子始终为 1。

O(log n)：称为对数复杂度

• 1 项：1 次操作
• 10 项：2 次操作
• 100 项：3 次操作
• 1000 项：4 次操作
• 10,000 项：5 次操作

计算次数仅增加输入值的对数。所以在这种情况下，假设每次计算需要 1 秒，输入的对数n就是所需的时间，因此log n.

这就是它的要点。他们减少了数学，所以它可能不完全是 n ²或他们所说的任何东西，但这将是缩放的主要因素。

Answer 3

Answer 4

编辑：快速说明，这几乎肯定会将Big O 表示法（它是一个上限）与 Theta 表示法（它既是上限又是下限）混淆。以我的经验，这实际上是非学术环境中的典型讨论。对造成的任何混乱表示歉意。

一句话：随着你的工作规模越来越大，完成它需要多长时间？

显然，这只是使用“大小”作为输入，“所用时间”作为输出——如果你想谈论内存使用等，同样的想法也适用。

这是一个示例，我们有 N 件 T 恤要烘干。我们假设让它们处于干燥位置非常快（即人为交互可以忽略不计）。当然，现实生活中并非如此……

• 在外面使用晾衣绳：假设您有一个无限大的后院，洗涤物在 O(1) 时间内干燥。不管你有多少，它都会得到同样的阳光和新鲜空气，所以大小不会影响干燥时间。

• 使用滚筒式干衣机：您在每个负载中放入 10 件衬衫，然后它们在一个小时后完成。（忽略这里的实际数字——它们无关紧要。）因此，烘干 50 件衬衫所需的时间大约是烘干 10 件衬衫所需时间的 5 倍。

• 把所有东西都放在一个晾晒的柜子里：如果我们把所有东西都放在一大堆里，让一般的温暖来做，中间的衬衫需要很长时间才能变干。我不想猜测细节，但我怀疑这至少是 O(N^2) - 随着洗涤负荷的增加，干燥时间增加得更快。

“大 O”表示法的一个重要方面是它没有说明对于给定大小哪种算法更快。采用哈希表（字符串键，整数值）与对数组（字符串，整数）。基于字符串在哈希表中查找键或数组中的元素是否更快？（即对于数组，“找到字符串部分与给定键匹配的第一个元素。”）哈希表通常是摊销的（~=“平均”）O（1）——一旦它们被设置，它应该花费大约在 100 个条目表中查找条目与在 1,000,000 个条目表中查找条目的时间相同。在数组中查找元素（基于内容而不是索引）是线性的，即 O(N) — 平均而言，您将不得不查看一半的条目。

这是否使哈希表比查找数组更快？不必要。如果您有一个非常小的条目集合，那么数组可能会更快 - 您可以在计算您正在查看的字符串的哈希码所需的时间内检查所有字符串。然而，随着数据集变大，哈希表最终将击败数组。

Answer 5

Big O 描述了当输入变大时函数增长行为的上限，例如程序的运行时间。

例子：

• O(n)：如果我将输入大小加倍，则运行时间加倍

• O(n ² )：如果输入大小翻倍，则运行时翻四倍

• O(log n)：如果输入大小翻倍，则运行时间增加一

• O(2 ⁿ )：如果输入大小增加一，运行时间加倍

输入大小通常是表示输入所需的位空间。

Answer 6

Big O notation is most commonly used by programmers as an approximate measure of how long a computation (algorithm) will take to complete expressed as a function of the size of the input set.

Big O is useful to compare how well two algorithms will scale up as the number of inputs is increased.

More precisely Big O notation is used to express the asymptotic behavior of a function. That means how the function behaves as it approaches infinity.

In many cases the "O" of an algorithm will fall into one of the following cases:

• O(1) - Time to complete is the same regardless of the size of input set. An example is accessing an array element by index.
• O(Log N) - Time to complete increases roughly in line with the log2(n). For example 1024 items takes roughly twice as long as 32 items, because Log2(1024) = 10 and Log2(32) = 5. An example is finding an item in a binary search tree (BST).
• O(N) - Time to complete that scales linearly with the size of the input set. In other words if you double the number of items in the input set, the algorithm takes roughly twice as long. An example is counting the number of items in a linked list.
• O(N Log N) - Time to complete increases by the number of items times the result of Log2(N). An example of this is heap sort and quick sort.
• O(N^2) - Time to complete is roughly equal to the square of the number of items. An example of this is bubble sort.
• O(N!) - Time to complete is the factorial of the input set. An example of this is the traveling salesman problem brute-force solution.

Big O ignores factors that do not contribute in a meaningful way to the growth curve of a function as the input size increases towards infinity. This means that constants that are added to or multiplied by the function are simply ignored.

Answer 7

Big O 只是一种以常见方式“表达”自己的方式，“运行我的代码需要多少时间/空间？”。

你可能经常看到 O(n)、O(n ² )、O(nlogn) 等等，这些只是展示的方式；算法如何变化？

O(n) 表示大 O 是 n，现在你可能会想，“n 是什么！？” 那么“n”是元素的数量。成像您要在数组中搜索项目。您必须查看每个元素并作为“您是正确的元素/项目吗？” 在最坏的情况下，该项目位于最后一个索引处，这意味着它花费的时间与列表中的项目一样多，所以为了通用，我们说“哦，嘿，n 是一个公平的给定数量的值！” .

那么您可能会理解“n ² ”的含义，但更具体地说，请考虑一下您有一个简单、最简单的排序算法；冒泡排序。该算法需要针对每个项目查看整个列表。

我的列表

1. 1
2. 6
3. 3

这里的流程是：

• 比较 1 和 6，哪个最大？Ok 6 位置正确，继续前进！
• 比较 6 和 3，哦，3 少了！让我们移动它，好吧，列表改变了，我们需要从头开始！

这是 On n ²因为，您需要查看列表中的所有项目，其中有“n”个项目。对于每个项目，你再看一遍所有项目，为了比较，这也是“n”，所以对于每个项目，你看“n”次，意思是 n*n = n ²

我希望这和你想要的一样简单。

但请记住，Big O 只是一种以时空方式表达自己的方式。

Answer 8

Big O 描述了算法的基本缩放性质。

Big O 没有告诉你关于给定算法的很多信息。它切入骨干，仅提供有关算法缩放性质的信息，特别是算法的资源使用（思考时间或内存）如何响应“输入大小”而缩放。

考虑蒸汽机和火箭之间的区别。它们不仅是同一事物的不同品种（例如，普锐斯发动机与兰博基尼发动机），而且它们的核心是截然不同的推进系统。蒸汽机可能比玩具火箭快，但没有蒸汽活塞发动机能够达到轨道运载火箭的速度。这是因为这些系统在达到给定速度（“输入大小”）所需的燃料（“资源使用”）关系方面具有不同的缩放特性。

为什么这个这么重要？因为软件处理的问题的大小可能相差多达一万亿倍。考虑一下。前往月球所需的速度与人类步行速度之间的比率小于 10,000:1，与软件可能面临的输入大小范围相比，这绝对是微不足道的。并且由于软件可能面临输入大小的天文数字范围，因此算法的大 O 复杂性（它是基本的缩放性质）可能胜过任何实现细节。

考虑规范排序示例。冒泡排序是 O(n ² )，而合并排序是 O(n log n)。假设您有两个排序应用程序，应用程序 A 使用冒泡排序，应用程序 B 使用合并排序，假设对于大约 30 个元素的输入大小，应用程序 A 在排序时比应用程序 B 快 1,000 倍。如果您不必对超过 30 个元素进行排序，那么显然您应该更喜欢应用程序 A，因为在这些输入大小下它要快得多。但是，如果您发现您可能需要对一千万个项目进行排序，那么您所期望的是，在这种情况下，应用程序 B 实际上最终比应用程序 A 快数千倍，这完全是由于每种算法的扩展方式。

Answer 9

Here is the plain English bestiary I tend to use when explaining the common varieties of Big-O

In all cases, prefer algorithms higher up on the list to those lower on the list. However, the cost of moving to a more expensive complexity class varies significantly.

O(1):

No growth. Regardless of how big as the problem is, you can solve it in the same amount of time. This is somewhat analogous to broadcasting where it takes the same amount of energy to broadcast over a given distance, regardless of the number of people that lie within the broadcast range.

O(log n):

This complexity is the same as O(1) except that it's just a little bit worse. For all practical purposes, you can consider this as a very large constant scaling. The difference in work between processing 1 thousand and 1 billion items is only a factor six.

O(n):

The cost of solving the problem is proportional to the size of the problem. If your problem doubles in size, then the cost of the solution doubles. Since most problems have to be scanned into the computer in some way, as data entry, disk reads, or network traffic, this is generally an affordable scaling factor.

O(n log n):

This complexity is very similar to O(n). For all practical purposes, the two are equivalent. This level of complexity would generally still be considered scalable. By tweaking assumptions some O(n log n) algorithms can be transformed into O(n) algorithms. For example, bounding the size of keys reduces sorting from O(n log n) to O(n).

O(n²):

Grows as a square, where n is the length of the side of a square. This is the same growth rate as the "network effect", where everyone in a network might know everyone else in the network. Growth is expensive. Most scalable solutions cannot use algorithms with this level of complexity without doing significant gymnastics. This generally applies to all other polynomial complexities - O(n^k) - as well.

O(2ⁿ):

Does not scale. You have no hope of solving any non-trivially sized problem. Useful for knowing what to avoid, and for experts to find approximate algorithms which are in O(n^k).

Answer 10

大 O 衡量算法相对于其输入大小使用了多少时间/空间。

如果算法是 O(n)，那么时间/空间将以与其输入相同的速率增加。

如果算法为 O(n ² )，则时间/空间以其输入平方的速率增加。

等等。

Answer 11

It is very difficult to measure the speed of software programs, and when we try, the answers can be very complex and filled with exceptions and special cases. This is a big problem, because all those exceptions and special cases are distracting and unhelpful when we want to compare two different programs with one another to find out which is "fastest".

As a result of all this unhelpful complexity, people try to describe the speed of software programs using the smallest and least complex (mathematical) expressions possible. These expressions are very very crude approximations: Although, with a bit of luck, they will capture the "essence" of whether a piece of software is fast or slow.

Because they are approximations, we use the letter "O" (Big Oh) in the expression, as a convention to signal to the reader that we are making a gross oversimplification. (And to make sure that nobody mistakenly thinks that the expression is in any way accurate).

If you read the "Oh" as meaning "on the order of" or "approximately" you will not go too far wrong. (I think the choice of the Big-Oh might have been an attempt at humour).

The only thing that these "Big-Oh" expressions try to do is to describe how much the software slows down as we increase the amount of data that the software has to process. If we double the amount of data that needs to be processed, does the software need twice as long to finish it's work? Ten times as long? In practice, there are a very limited number of big-Oh expressions that you will encounter and need to worry about:

The good:

• O(1) Constant: The program takes the same time to run no matter how big the input is.
• O(log n) Logarithmic: The program run-time increases only slowly, even with big increases in the size of the input.

The bad:

• O(n) Linear: The program run-time increases proportionally to the size of the input.
• O(n^k) Polynomial: - Processing time grows faster and faster - as a polynomial function - as the size of the input increases.

... and the ugly:

• O(k^n) Exponential The program run-time increases very quickly with even moderate increases in the size of the problem - it is only practical to process small data sets with exponential algorithms.
• O(n!) Factorial The program run-time will be longer than you can afford to wait for anything but the very smallest and most trivial-seeming datasets.

Answer 12

What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics.

A Plain English Explanation of the Need for Big-O Notation:

When we program, we are trying to solve a problem. What we code is called an algorithm. Big O notation allows us to compare the worse case performance of our algorithms in a standardized way. Hardware specs vary over time and improvements in hardware can reduce the time it takes an algorithms to run. But replacing the hardware does not mean our algorithm is any better or improved over time, as our algorithm is still the same. So in order to allow us to compare different algorithms, to determine if one is better or not, we use Big O notation.

A Plain English Explanation of What Big O Notation is:

Not all algorithms run in the same amount of time, and can vary based on the number of items in the input, which we'll call n. Based on this, we consider the worse case analysis, or an upper-bound of the run-time as n get larger and larger. We must be aware of what n is, because many of the Big O notations reference it.

Answer 13

Ok, my 2cents.

Big-O, is rate of increase of resource consumed by program, w.r.t. problem-instance-size

Resource : Could be total-CPU time, could be maximum RAM space. By default refers to CPU time.

Say the problem is "Find the sum",

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problem-instance= {5,10,15} ==> problem-instance-size = 3, iterations-in-loop= 3

problem-instance= {5,10,15,20,25} ==> problem-instance-size = 5 iterations-in-loop = 5

For input of size "n" the program is growing at speed of "n" iterations in array. Hence Big-O is N expressed as O(n)

Say the problem is "Find the Combination",

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problem-instance= {5,10,15} ==> problem-instance-size = 3, total-iterations = 3*3 = 9

problem-instance= {5,10,15,20,25} ==> problem-instance-size = 5, total-iterations= 5*5 =25

For input of size "n" the program is growing at speed of "n*n" iterations in array. Hence Big-O is N² expressed as O(n²)

Answer 14

A simple straightforward answer can be:

Big O represents the worst possible time/space for that algorithm. The algorithm will never take more space/time above that limit. Big O represents time/space complexity in the extreme case.

Answer 15

大 O 表示法是一种在空间或运行时间方面描述算法上限的方法。n 是问题中元素的数量（即数组的大小、树中的节点数等）。我们感兴趣的是描述随着 n 变大的运行时间。

当我们说某个算法是 O(f(n)) 时，我们是在说该算法的运行时间（或所需空间）总是低于某个常数时间 f(n)。

说二分查找的运行时间为 O(logn) 就是说存在一些常数 c，你可以将它乘以 log(n) 总是大于二分查找的运行时间。在这种情况下，您将始终有一些 log(n) 比较的常数因子。

换句话说，其中 g(n) 是算法的运行时间，我们说 g(n) = O(f(n)) 当 g(n) <= c*f(n) 当 n > k 时，其中c 和 k 是一些常数。

Answer 16

"What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics."

Such a beautifully simple and short question seems at least to deserve an equally short answer, like a student might receive during tutoring.

Big O notation simply tells how much time* an algorithm can run within, in terms of only the amount of input data**.

( *in a wonderful, unit-free sense of time!)
(**which is what matters, because people will always want more, whether they live today or tomorrow)

Well, what's so wonderful about Big O notation if that's what it does?

• Practically speaking, Big O analysis is so useful and important because Big O puts the focus squarely on the algorithm's own complexity and completely ignores anything that is merely a proportionality constant—like a JavaScript engine, the speed of a CPU, your Internet connection, and all those things which become quickly become as laughably outdated as a Model T. Big O focuses on performance only in the way that matters equally as much to people living in the present or in the future.

• Big O notation also shines a spotlight directly on the most important principle of computer programming/engineering, the fact which inspires all good programmers to keep thinking and dreaming: the only way to achieve results beyond the slow forward march of technology is to invent a better algorithm.

Answer 17

Algorithm example (Java):

public boolean search(/* for */Integer K,/* in */List</* of */Integer> L)
{
    for(/* each */Integer i:/* in */L)
    {
        if(i == K)
        {
            return true;
        }
    }
    
    return false;
}

Algorithm description:

• This algorithm searches a list, item by item, looking for a key,

• Iterating on each item in the list, if it's the key then return True,

• If the loop has finished without finding the key, return False.

Big-O notation represents the upper-bound on the Complexity (Time, Space, ..)

To find The Big-O on Time Complexity:

• Calculate how much time (regarding input size) the worst case takes:

• Worst-Case: the key doesn't exist in the list.

• Time(Worst-Case) = 4n+1

• Time: O(4n+1) = O(n) | in Big-O, constants are neglected

• O(n) ~ Linear

There's also Big-Omega, which represent the complexity of the Best-Case:

• Best-Case: the key is the first item.

• Time(Best-Case) = 4

• Time: Ω(4) = O(1) ~ Instant\Constant

Answer 18

Big O notation is a way of describing how quickly an algorithm will run given an arbitrary number of input parameters, which we'll call "n". It is useful in computer science because different machines operate at different speeds, and simply saying that an algorithm takes 5 seconds doesn't tell you much because while you may be running a system with a 4.5 Ghz octo-core processor, I may be running a 15 year old, 800 Mhz system, which could take longer regardless of the algorithm. So instead of specifying how fast an algorithm runs in terms of time, we say how fast it runs in terms of number of input parameters, or "n". By describing algorithms in this way, we are able to compare the speeds of algorithms without having to take into account the speed of the computer itself.

Answer 19

Big O

f(x) = O(g(x)) when x goes to a (for example, a = +∞) means that there is a function k such that:

1. f(x) = k(x)g(x)

2. k is bounded in some neighborhood of a (if a = +∞, this means that there are numbers N and M such that for every x > N, |k(x)| < M).

In other words, in plain English: f(x) = O(g(x)), x → a, means that in a neighborhood of a, f decomposes into the product of g and some bounded function.

Small o

By the way, here is for comparison the definition of small o.

f(x) = o(g(x)) when x goes to a means that there is a function k such that:

1. f(x) = k(x)g(x)

2. k(x) goes to 0 when x goes to a.

Examples

• sin x = O(x) when x → 0.

• sin x = O(1) when x → +∞,

• x² + x = O(x) when x → 0,

• x² + x = O(x²) when x → +∞,

• ln(x) = o(x) = O(x) when x → +∞.

Attention! The notation with the equal sign "=" uses a "fake equality": it is true that o(g(x)) = O(g(x)), but false that O(g(x)) = o(g(x)). Similarly, it is ok to write "ln(x) = o(x) when x → +∞", but the formula "o(x) = ln(x)" would make no sense.

More examples

• O(1) = O(n) = O(n²) when n → +∞ (but not the other way around, the equality is "fake"),

• O(n) + O(n²) = O(n²) when n → +∞</p>

• O(O(n²)) = O(n²) when n → +∞</p>

• O(n²)O(n³) = O(n⁵) when n → +∞</p>

---

Here is the Wikipedia article: https://en.wikipedia.org/wiki/Big_O_notation

Answer 20

You want to know all there is to know of big O? So do I.

So to talk of big O, I will use words that have just one beat in them. One sound per word. Small words are quick. You know these words, and so do I. We will use words with one sound. They are small. I am sure you will know all of the words we will use!

Now, let’s you and me talk of work. Most of the time, I do not like work. Do you like work? It may be the case that you do, but I am sure I do not.

I do not like to go to work. I do not like to spend time at work. If I had my way, I would like just to play, and do fun things. Do you feel the same as I do?

Now at times, I do have to go to work. It is sad, but true. So, when I am at work, I have a rule: I try to do less work. As near to no work as I can. Then I go play!

So here is the big news: the big O can help me not to do work! I can play more of the time, if I know big O. Less work, more play! That is what big O helps me do.

Now I have some work. I have this list: one, two, three, four, five, six. I must add all things in this list.

Wow, I hate work. But oh well, I have to do this. So here I go.

One plus two is three… plus three is six... and four is... I don’t know. I got lost. It is too hard for me to do in my head. I don’t much care for this kind of work.

So let's not do the work. Let's you and me just think how hard it is. How much work would I have to do, to add six numbers?

Well, let’s see. I must add one and two, and then add that to three, and then add that to four… All in all, I count six adds. I have to do six adds to solve this.

Here comes big O, to tell us just how hard this math is.

Big O says: we must do six adds to solve this. One add, for each thing from one to six. Six small bits of work... each bit of work is one add.

Well, I will not do the work to add them now. But I know how hard it would be. It would be six adds.

Oh no, now I have more work. Sheesh. Who makes this kind of stuff?!

Now they ask me to add from one to ten! Why would I do that? I did not want to add one to six. To add from one to ten… well… that would be even more hard!

How much more hard would it be? How much more work would I have to do? Do I need more or less steps?

Well, I guess I would have to do ten adds… one for each thing from one to ten. Ten is more than six. I would have to work that much more to add from one to ten, than one to six!

I do not want to add right now. I just want to think on how hard it might be to add that much. And, I hope, to play as soon as I can.

To add from one to six, that is some work. But do you see, to add from one to ten, that is more work?

Big O is your friend and mine. Big O helps us think on how much work we have to do, so we can plan. And, if we are friends with big O, he can help us choose work that is not so hard!

Now we must do new work. Oh, no. I don’t like this work thing at all.

The new work is: add all things from one to n.

Wait! What is n? Did I miss that? How can I add from one to n if you don’t tell me what n is?

Well, I don’t know what n is. I was not told. Were you? No? Oh well. So we can’t do the work. Whew.

But though we will not do the work now, we can guess how hard it would be, if we knew n. We would have to add up n things, right? Of course!

Now here comes big O, and he will tell us how hard this work is. He says: to add all things from one to N, one by one, is O(n). To add all these things, [I know I must add n times.][1] That is big O! He tells us how hard it is to do some type of work.

To me, I think of big O like a big, slow, boss man. He thinks on work, but he does not do it. He might say, "That work is quick." Or, he might say, "That work is so slow and hard!" But he does not do the work. He just looks at the work, and then he tells us how much time it might take.

I care lots for big O. Why? I do not like to work! No one likes to work. That is why we all love big O! He tells us how fast we can work. He helps us think of how hard work is.

Uh oh, more work. Now, let’s not do the work. But, let’s make a plan to do it, step by step.

They gave us a deck of ten cards. They are all mixed up: seven, four, two, six… not straight at all. And now... our job is to sort them.

Ergh. That sounds like a lot of work!

How can we sort this deck? I have a plan.

I will look at each pair of cards, pair by pair, through the deck, from first to last. If the first card in one pair is big and the next card in that pair is small, I swap them. Else, I go to the next pair, and so on and so on... and soon, the deck is done.

When the deck is done, I ask: did I swap cards in that pass? If so, I must do it all once more, from the top.

At some point, at some time, there will be no swaps, and our sort of the deck would be done. So much work!

Well, how much work would that be, to sort the cards with those rules?

I have ten cards. And, most of the time -- that is, if I don’t have lots of luck -- I must go through the whole deck up to ten times, with up to ten card swaps each time through the deck.

Big O, help me!

Big O comes in and says: for a deck of n cards, to sort it this way will be done in O(N squared) time.

Why does he say n squared?

Well, you know n squared is n times n. Now, I get it: n cards checked, up to what might be n times through the deck. That is two loops, each with n steps. That is n squared much work to be done. A lot of work, for sure!

Now when big O says it will take O(n squared) work, he does not mean n squared adds, on the nose. It might be some small bit less, for some case. But in the worst case, it will be near n squared steps of work to sort the deck.

Now here is where big O is our friend.

Big O points out this: as n gets big, when we sort cards, the job gets MUCH MUCH MORE HARD than the old just-add-these-things job. How do we know this?

Well, if n gets real big, we do not care what we might add to n or n squared.

For big n, n squared is more large than n.

Big O tells us that to sort things is more hard than to add things. O(n squared) is more than O(n) for big n. That means: if n gets real big, to sort a mixed deck of n things MUST take more time, than to just add n mixed things.

Big O does not solve the work for us. Big O tells us how hard the work is.

I have a deck of cards. I did sort them. You helped. Thanks.

Is there a more fast way to sort the cards? Can big O help us?

Yes, there is a more fast way! It takes some time to learn, but it works... and it works quite fast. You can try it too, but take your time with each step and do not lose your place.

In this new way to sort a deck, we do not check pairs of cards the way we did a while ago. Here are your new rules to sort this deck:

One: I choose one card in the part of the deck we work on now. You can choose one for me if you like. (The first time we do this, “the part of the deck we work on now” is the whole deck, of course.)

Two: I splay the deck on that card you chose. What is this splay; how do I splay? Well, I go from the start card down, one by one, and I look for a card that is more high than the splay card.

Three: I go from the end card up, and I look for a card that is more low than the splay card.

Once I have found these two cards, I swap them, and go on to look for more cards to swap. That is, I go back to step Two, and splay on the card you chose some more.

At some point, this loop (from Two to Three) will end. It ends when both halves of this search meet at the splay card. Then, we have just splayed the deck with the card you chose in step One. Now, all the cards near the start are more low than the splay card; and the cards near the end are more high than the splay card. Cool trick!

Four (and this is the fun part): I have two small decks now, one more low than the splay card, and one more high. Now I go to step one, on each small deck! That is to say, I start from step One on the first small deck, and when that work is done, I start from step One on the next small deck.

I break up the deck in parts, and sort each part, more small and more small, and at some time I have no more work to do. Now this may seem slow, with all the rules. But trust me, it is not slow at all. It is much less work than the first way to sort things!

What is this sort called? It is called Quick Sort! That sort was made by a man called C. A. R. Hoare and he called it Quick Sort. Now, Quick Sort gets used all the time!

Quick Sort breaks up big decks in small ones. That is to say, it breaks up big tasks in small ones.

Hmmm. There may be a rule in there, I think. To make big tasks small, break them up.

This sort is quite quick. How quick? Big O tells us: this sort needs O(n log n) work to be done, in the mean case.

Is it more or less fast than the first sort? Big O, please help!

The first sort was O(n squared). But Quick Sort is O(n log n). You know that n log n is less than n squared, for big n, right? Well, that is how we know that Quick Sort is fast!

If you have to sort a deck, what is the best way? Well, you can do what you want, but I would choose Quick Sort.

Why do I choose Quick Sort? I do not like to work, of course! I want work done as soon as I can get it done.

How do I know Quick Sort is less work? I know that O(n log n) is less than O(n squared). The O's are more small, so Quick Sort is less work!

Now you know my friend, Big O. He helps us do less work. And if you know big O, you can do less work too!

You learned all that with me! You are so smart! Thank you so much!

Now that work is done, let’s go play!

---

[1]: There is a way to cheat and add all the things from one to n, all at one time. Some kid named Gauss found this out when he was eight. I am not that smart though, so don't ask me how he did it.

Answer 21

Not sure I'm further contributing to the subject but still thought I'd share: I once found this blog post to have some quite helpful (though very basic) explanations & examples on Big O:

Via examples, this helped get the bare basics into my tortoiseshell-like skull, so I think it's a pretty descent 10-minute read to get you headed in the right direction.

Answer 22

Assume we're talking about an algorithm A, which should do something with a dataset of size n.

Then O( <some expression X involving n> ) means, in simple English:

If you're unlucky when executing A, it might take as much as X(n) operations to complete.

As it happens, there are certain functions (think of them as implementations of X(n)) that tend to occur quite often. These are well known and easily compared (Examples: 1, Log N, N, N^2, N!, etc..)

By comparing these when talking about A and other algorithms, it is easy to rank the algorithms according to the number of operations they may (worst-case) require to complete.

In general, our goal will be to find or structure an algorithm A in such a way that it will have a function X(n) that returns as low a number as possible.

Answer 23

I've more simpler way to understand the time complexity he most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N as N approaches infinity. In general you can think of it like this:

statement;

Is constant. The running time of the statement will not change in relation to N

for ( i = 0; i < N; i++ )
  statement;

Is linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

Is quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

Is logarithmic. The running time of the algorithm is proportional to the number of times N can be divided by 2. This is because the algorithm divides the working area in half with each iteration.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

Is N * log ( N ). The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic.

In general, doing something with every item in one dimension is linear, doing something with every item in two dimensions is quadratic, and dividing the working area in half is logarithmic. There are other Big O measures such as cubic, exponential, and square root, but they're not nearly as common. Big O notation is described as O ( ) where is the measure. The quicksort algorithm would be described as O ( N * log ( N ) ).

Note: None of this has taken into account best, average, and worst case measures. Each would have its own Big O notation. Also note that this is a VERY simplistic explanation. Big O is the most common, but it's also more complex that I've shown. There are also other notations such as big omega, little o, and big theta. You probably won't encounter them outside of an algorithm analysis course.

• See more at: Here

Answer 24

If you have a suitable notion of infinity in your head, then there is a very brief description:

Big O notation tells you the cost of solving an infinitely large problem.

And furthermore

Constant factors are negligible

If you upgrade to a computer that can run your algorithm twice as fast, big O notation won't notice that. Constant factor improvements are too small to even be noticed in the scale that big O notation works with. Note that this is an intentional part of the design of big O notation.

Although anything "larger" than a constant factor can be detected, however.

When interested in doing computations whose size is "large" enough to be considered as approximately infinity, then big O notation is approximately the cost of solving your problem.

---

If the above doesn't make sense, then you don't have a compatible intuitive notion of infinity in your head, and you should probably disregard all of the above; the only way I know to make these ideas rigorous, or to explain them if they aren't already intuitively useful, is to first teach you big O notation or something similar. (although, once you well understand big O notation in the future, it may be worthwhile to revisit these ideas)

Answer 25

Say you order Harry Potter: Complete 8-Film Collection [Blu-ray] from Amazon and download the same film collection online at the same time. You want to test which method is faster. The delivery takes almost a day to arrive and the download completed about 30 minutes earlier. Great! So it’s a tight race.

What if I order several Blu-ray movies like The Lord of the Rings, Twilight, The Dark Knight Trilogy, etc. and download all the movies online at the same time? This time, the delivery still take a day to complete, but the online download takes 3 days to finish. For online shopping, the number of purchased item (input) doesn’t affect the delivery time. The output is constant. We call this O(1).

For online downloading, the download time is directly proportional to the movie file sizes (input). We call this O(n).

From the experiments, we know that online shopping scales better than online downloading. It is very important to understand big O notation because it helps you to analyze the scalability and efficiency of algorithms.

Note: Big O notation represents the worst-case scenario of an algorithm. Let’s assume that O(1) and O(n) are the worst-case scenarios of the example above.

Reference : http://carlcheo.com/compsci

Answer 26

What is a plain English explanation of “Big O” notation?

Very Quick Note:

The O in "Big O" refers to as "Order"(or precisely "order of")
so you could get its idea literally that it's used to order something to compare them.

• "Big O" does two things:

  1. Estimates how many steps of the method your computer applies to accomplish a task.
  2. Facilitate the process to compare with others in order to determine whether it's good or not?
  3. "Big O' achieves the above two with standardized Notations.

• There are seven most used notations

  1. O(1), means your computer gets a task done with 1 step, it's excellent, Ordered No.1
  2. O(logN), means your computer complete a task with logN steps, its good, Ordered No.2
  3. O(N), finish a task with N steps, its fair, Order No.3
  4. O(NlogN), ends a task with O(NlogN) steps, it's not good, Order No.4
  5. O(N^2), get a task done with N^2 steps, it's bad, Order No.5
  6. O(2^N), get a task done with 2^N steps, it's horrible, Order No.6
  7. O(N!), get a task done with N! steps, it's terrible, Order No.7

Suppose you get notation O(N^2), not only you are clear the method takes N*N steps to accomplish a task, also you see that it's not good as O(NlogN) from its ranking.

Please note the order at line end, just for your better understanding.There's more than 7 notations if all possibilities considered.

In CS, the set of steps to accomplish a task is called algorithms.
In Terminology, Big O notation is used to describe the performance or complexity of an algorithm.

In addition, Big O establishes the worst-case or measure the Upper-Bound steps.
You could refer to Big-Ω (Big-Omega) for best case.

Big-Ω (Big-Omega) notation (article) | Khan Academy

• Summary
  "Big O" describes the algorithm's performance and evaluates it.

  or address it formally, "Big O" classifies the algorithms and standardize the comparison process.

Answer 27

Definition :- Big O notation is a notation which says how a algorithm performance will perform if the data input increases.

When we talk about algorithms there are 3 important pillars Input , Output and Processing of algorithm. Big O is symbolic notation which says if the data input is increased in what rate will the performance vary of the algorithm processing.

I would encourage you to see this youtube video which explains Big O Notation in depth with code examples.

So for example assume that a algorithm takes 5 records and the time required for processing the same is 27 seconds. Now if we increase the records to 10 the algorithm takes 105 seconds.

In simple words the time taken is square of the number of records. We can denote this by O(n ^ 2). This symbolic representation is termed as Big O notation.

Now please note the units can be anything in inputs it can be bytes , bits number of records , the performance can be measured in any unit like second , minutes , days and so on. So its not the exact unit but rather the relationship.

For example look at the below function "Function1" which takes a collection and does processing on the first record. Now for this function the performance will be same irrespective you put 1000 , 10000 or 100000 records. So we can denote it by O(1).

void Function1(List<string> data)
{
string str = data[0];
}

Now see the below function "Function2()". In this case the processing time will increase with number of records. We can denote this algorithm performance using O(n).

void Function2(List<string> data)
        {
            foreach(string str in data)
            {
                if (str == "shiv")
                {
                    return;
                }
            }
        }

When we see a Big O notation for any algorithm we can classify them in to three categories of performance :-

1. Log and constant category :- Any developer would love to see their algorithm performance in this category.
2. Linear :- Developer will not want to see algorithms in this category , until its the last option or the only option left.
3. Exponential :- This is where we do not want to see our algorithms and a rework is needed.

So by looking at Big O notation we categorize good and bad zones for algorithms.

I would recommend you to watch this 10 minutes video which discusses Big O with sample code

https://www.youtube.com/watch?v=k6kxtzICG_g

Answer 28

Simplest way to look at it (in plain English)

We are trying to see how the number of input parameters, affects the running time of an algorithm. If the running time of your application is proportional to the number of input parameters, then it is said to be in Big O of n.

The above statement is a good start but not completely true.

A more accurate explanation (mathematical)

Suppose

n=number of input parameters

T(n)= The actual function that expresses the running time of the algorithm as a function of n

c= a constant

f(n)= An approximate function that expresses the running time of the algorithm as a function of n

Then as far as Big O is concerned, the approximation f(n) is considered good enough as long as the below condition is true.

lim     T(n) ≤ c×f(n)
n→∞

The equation is read as As n approaches infinity, T of n, is less than or equal to c times f of n.

In big O notation this is written as

T(n)∈O(n)

This is read as T of n is in big O of n.

Back to English

Based on the mathematical definition above, if you say your algorithm is a Big O of n, it means it is a function of n (number of input parameters) or faster. If your algorithm is Big O of n, then it is also automatically the Big O of n square.

Big O of n means my algorithm runs at least as fast as this. You cannot look at Big O notation of your algorithm and say its slow. You can only say its fast.

Check this out for a video tutorial on Big O from UC Berkley. It is actually a simple concept. If you hear professor Shewchuck (aka God level teacher) explaining it, you will say "Oh that's all it is!".

Answer 29

I found a really great explanation about big O notation especially for a someone who's not much into mathematics.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

Anyone who's read Programming Pearls or any other Computer Science books and doesn’t have a grounding in Mathematics will have hit a wall when they reached chapters that mention O(N log N) or other seemingly crazy syntax. Hopefully this article will help you gain an understanding of the basics of Big O and Logarithms.

As a programmer first and a mathematician second (or maybe third or fourth) I found the best way to understand Big O thoroughly was to produce some examples in code. So, below are some common orders of growth along with descriptions and examples where possible.

O(1)

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}

O(N)

O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O(N²)

O(N²) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N³), O(N⁴) etc.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O(2^N)

O(2^N) denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2^N) function is exponential - starting off very shallow, then rising meteorically. An example of an O(2^N) function is the recursive calculation of Fibonacci numbers:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Logarithms

Logarithms are slightly trickier to explain so I'll use a common example:

Binary search is a technique used to search sorted data sets. It works by selecting the middle element of the data set, essentially the median, and compares it against a target value. If the values match it will return success. If the target value is higher than the value of the probe element it will take the upper half of the data set and perform the same operation against it. Likewise, if the target value is lower than the value of the probe element it will perform the operation against the lower half. It will continue to halve the data set with each iteration until the value has been found or until it can no longer split the data set.

This type of algorithm is described as O(log N). The iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase e.g. an input data set containing 10 items takes one second to complete, a data set containing 100 items takes two seconds, and a data set containing 1000 items will take three seconds. Doubling the size of the input data set has little effect on its growth as after a single iteration of the algorithm the data set will be halved and therefore on a par with an input data set half the size. This makes algorithms like binary search extremely efficient when dealing with large data sets.

Answer 30

This is a very simplified explanation, but I hope it covers most important details.

Let's say your algorithm dealing with the problem depends on some 'factors', for example let's make it N and X.

Depending on N and X, your algorithm will require some operations, for example in the WORST case it's 3(N^2) + log(X) operations.

Since Big-O doesn't care too much about constant factor (aka 3), the Big-O of your algorithm is O(N^2 + log(X)). It basically translates 'the amount of operations your algorithm needs for the worst case scales with this'.

Answer 31

Preface

algorithm: procedure/formula for solving a problem

---

How do analyze algorithms and how can we compare algorithms against each other?

example: you and a friend are asked to create a function to sum the numbers from 0 to N. You come up with f(x) and your friend comes up with g(x). Both functions have the same result, but a different algorithm. In order to objectively compare the efficiency of the algorithms we use Big-O notation.

Big-O notation: describes how quickly runtime will grow relative to the input as the input get arbitrarily large.

3 key takeaways:

1. Compare how quickly runtime grows NOT compare exact runtimes (depends on hardware)
2. Only concerned with runtime grow relative to the input (n)
3. As n gets arbitrarily large, focus on the terms that will grow the fastest as n gets large (think infinity) AKA asymptotic analysis

Space complexity: aside from time complexity, we also care about space complexity (how much memory/space an algorithm uses). Instead of checking the time of operations, we check the size of the allocation of memory.

Answer 32

Big O is a means to represent the upper bounds of any function. We generally use it for expressing the upper bounds of a function that tells the running time of an Algorithm.

Ex : f(n) = 2(n^2) +3n be a function representing the running time of a hypothetical algorithm, Big-O notation essentially gives the upper limit for this function which is O(n^2)

This notation basically tells us that, for any input 'n' the running time won't be greater than the value expressed by Big-O notation.

Also, agree with all the above detailed answers. Hope this helps !!

Answer 33

Big O is describing a class of functions.

It describes how fast functions grow for big input values.

For a given function f, O(f) descibes all functions g(n) for which you can find an n0 and a constant c so that all values of g(n) with n >= n0 are less or equal to c*f(n)

In less mathematical words O(f) is a set of functions. Namely all functions, that from some value n0 onwards, are growing slower or as fast as f.

If f(n) = n then

g(n) = 3n is in O(f).Because constant factors do not matter h(n) = n+1000 is in O(f) because it might be bigger for all values smaler than 1000 but for big O only huge inputs matter.

However i(n) = n^2 is not in O(f) because a quadratic funcion grows faster than a linear one.

Answer 34

It represents the speed of an algorithm in the long run.

To take a literal analogy, you don't care how fast a runner can sprint a 100m dash, or even a 5k run. You care more about marathoners, and preferably ultra marathoners (beyond which the analogy to running breaks down and you have to revert to the metaphorical meaning of "the long run").

You can safely stop reading here.

I'm adding this answer because I'm surprised how mathematical and technical the rest of the answers are. The notion of the "long run" in first sentence is related to the arbitrarily time-consuming computational tasks. Unlike running, which is limited by human capacity, computational tasks can take even more than millions of years for certain algorithms to complete.

What about all those mathematical logarithms and polynomials? It turns out that algorithms are intrinsically related to these mathematical terms. If you are measuring the heights of all the kids on the block, it will take you as much time as there are kids. This is intrinsically related to the notion of n^1 or just n where n is nothing more than the number of kids on the block. In the ultra-marathon case, you are measuring the heights of all the kids in your city, but you then have to ignore travel times and assume they are all available to you in a line (otherwise we jump ahead of the current explanation).

Suppose then you are trying to arrange the list that you made of of kids heights in order of shortest height to longest height. If it is just the kids in your neighborhood you might just eyeball it and come up with the ordered list. This is the "sprint" analogy, and we truly don't care about sprints in computer science because why use a computer when you can eyeball something?

But if you were arranging the list of the heights of all kids in your city, or better yet, your country, then you will find that how you do it is intrinsically tied to the mathematical log and n^2. Going through your list to find the shortest kid, writing his name in a separate notebook, and crossing it out from the original notebook is intrinsically tied to the mathematical n^2. If you think of arranging half your notebook, then the other half, and then combining the results, you will arrive at a method that is intrinsically tied to the logarithm.

Finally, suppose you first had to go to the store to buy a measuring tape. This is an example of an effort that is of consequence in short sprints, such as measuring the kids on the block, but when you are measuring all the kids in the city you can safely ignore this cost. This is the intrinsic connection to the mathematical dropping of say lower order polynomial terms.

I hope I have explained that the big-O notation is merely about the long run, that the mathematics is inherently connected to ways of computation, and that the dropping of mathematical terms and other simplifications are connected to the long run in a rather common sense way.

Once you realize this, you'll find the big-O is really super-easy because all the hard high school math just drops out easily. The only difficult part is analyzing an algorithm to identify the mathematical terms, but with some practice you can start dropping terms during the analysis itself and safely ignore chunks of the algorithm to focus only on the part that is relevant to the big-O. I. e. you should be able to eyeball most situations.

Happy big-O-ing, it was my favorite thing about Computer Science -- finding that something was way easier than I thought, and then being able to show off at Google interviews when the uninitiated would be intimidated, lol.

Answer 35

Big O in plain english is like <= (less than or equal). When we say for two functions f and g, f = O(g) it means that f <= g.

However, this does not mean that for any n f(n) <= g(n). Actually what it means is that f is less than or equal to g in terms of growth. It means that after a point f(n) <= c*g(n) if c is a constant. And after a point means than for all n >= n0 where n0 is another constant.

Answer 36

Big O - Economic Point of View.

My favourite English word to describe this concept is the price you pay for a task as it grows larger.

Think of it as recurring costs instead of fixed costs that you would pay at the beginning. The fixed costs become negligible in the big picture because costs only grow and they add up. We want to measure how fast they would grow and how soon they would add up with respect to the raw material we give to the set up - size of the problem.

However, if initial set up costs are high and you only produce a small amount of the product, you would want to look at these initial costs - they are also called the constants.

Since, these constants don't matter in the long run, this language allows us to discuss tasks beyond what kind of infrastructure we are running it on. So, the factories can be anywhere and the workers can be whoever - it's all gravy. But the size of the factory and the number of workers would be the things we could vary in the long run as your inputs and outputs grow.

Hence, this becomes a big picture approximation of how much you would have to spend to run something. Since time and space are the economic quantities (i.e. they are limited) here, they can both be expressed using this language.

Technical notes: Some examples of time complexity - O(n) generally means that if a problem is of size 'n', I at least have to see everything. O(log n) generally means that I halve the size of the problem and check and repeat until the task is done. O(n^2) means I need to look at pairs of things (like handshakes at a party between n people).

Answer 37

If I want to explain this to 6 years old child I will start to draw some functions f(x) = x and f(x) = x^2 for example and ask a child which function will be the upper function on the top of the page. Then we will proceed with drawing and see that x^2 wins. "Who wins" actually is the function which grows faster when x tends to infinity. So "function x is in Big O of x^2" means that x grows slower than x^2 when x tends to infinity. The same can be done when x tends to 0. If we draw these two function for x from 0 to 1 x will be an upper function, so "function x^2 is in Big O of x for x tends to 0". When the child will get older I add that really Big O can be a function which grows not faster but the same way as given function. Moreover constant is discarded. So 2x is in Big O of x.

Answer 38

What is a plain English explanation of “Big O” notation?

I would like to stress that the driving motive for “Big O” notation is one thing, when an input size of algorithm gets too big some parts (i.e constants, coefficients, terms )of the equation describing the measure of the algorithm becomes so insignificant that we ignore them. The parts of equation that survives after ignoring some of its parts is termed as the “Big O” notation of the algorithm.

So if the input size is NOT too big the idea of “Big O” notation( upper bound ) will be unimportant.

Les say you want to quantify the performance of the following algorithm

int sumArray (int[] nums){
    int sum=0;   // taking initialization and assignments n=1
    for(int i=0;nums.length;i++){
        sum += nums[i]; // taking initialization and assignments n=1
    }
    return sum;
}

In above algorithm, lets say you find out T(n) as follows (time complexity):

T(n) = 2*n + 2

To find its “Big O” notation, we need to consider very big input size:

n= 1,000,000   -> T(1,000,000) = 2,000,002
n=1,000,000,000  -> T(1,000,000,000) = 2,000,000,002
n=10,000,000,000  -> T(10,000,000,000) = 20,000,000,002

Lets give this similar inputs for another function F(n) = n

n= 1,000,000   -> F(1,000,000) = 1,000,000 
n=1,000,000,000  -> F(1,000,000,000) = 1,000,000,000
n=10,000,000,000  -> F(10,000,000,000) = 10,000,000,000

As you can see as input size get too big the T(n) approximately equal to or getting closer to F(n), so the constant 2 and the coefficient 2 are becoming too insignificant, now the idea of Big O” notation comes in,

O(T(n)) = F(n)
O(T(n)) = n

We say the big O of T(n) is n, and the notation is O(T(n)) = n, it is the upper bound of T(n) as n gets too big. the same step applies for other algorithms.

Answer 39

There are some great answers already posted, but I would like to contribute in a different way. If you want to visualize what all is happening you can assume that a compiler can perform close to 10^8 operations in ~1sec. If the input is given in 10^8, you might want to design an algorithm that operates in a linear fashion(like an un-nested for-loop). below is the table that can help you to quickly figure out the type of algorithm you want to figure out ;)

Answer 40

When we have a function like f(n) = n+3 and we want to know how the graph looks likes when n approaches infinity, we just drop all the constants and lower order terms because they don't matter when n gets big. Which leaves us with f(n) = n, so why can't we just use this, why do we need to look for some function which is above and below our f(n) = n+3 function, so big O and big Omega.

Because it would be incorrect to say that the function is just f(n) = n when n approaches infinity, so to be correct we describe the area where the f(n) = n+3 could be. We are not interested where the graph is exactly, because lower order terms and constant don't change the growth of the graph significantly, so in other words the area which is enclosed from upper and lower bound is a vague version of our f(n) = n+3 function.

The mere dropping of the constant and lower order term is exactly the process of finding the function which is below and above.

By definition is a function a lower or upper bound of another function if you can find a constant with whom you can multiply the f(n) = n function so that for every n the output is bigger (or smaller for lower bound) than for the original function:

f(n) = n*C > f(n) = n+3

And yes C = 2 would do it, therefore our function f(n) = n can be an upper bound of our f(x) = x+3 function.

Same for lower bound:

f(n) = n*C < f(n) = n+3

C = -2 would do it

So f(x) = n is the upper and lower bound of f(x) = x+3, when its both big O and Omega than its Theta, which means its tightly bound.

So big O could also be f(x) = x^2 because it fulfills the condition f(n) = n^2*C > f(n) = n+3. Its above our f(n) = n+3 graph, but the area between this upper bound and the lower bound is not as precise as our earlier bounds.

Answer 41

TLDR: Big O explains performance of an algorithm in mathematical terms.

Slower algorithms tend to run at n to the power of x or many, depending on depth of it, whereas faster ones like binary search run at O(log n), which makes it run faster as data set gets larger. Big O could be explained with other terms using n, or not even using n too (ie: O(1) ).

One can calculate Big O Looking at the most complex lines of the algorithm.

With small or unsorted datasets Big O can be surprising, as n log n complexity algorithms like binary search can be slow for smaller or unsorted sets, for a simple running example of linear search versus binary search, take a look at my JavaScript example:

https://codepen.io/serdarsenay/pen/XELWqN?editors=1011 (algorithms written below)

function lineerSearch() {
  init();
  var t = timer('lineerSearch benchmark');
  var input = this.event.target.value;
  for(var i = 0;i<unsortedhaystack.length - 1;i++) {
    if (unsortedhaystack[i] === input) {
      document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return unsortedhaystack[i]; 
    }
  }
}

function binarySearch () {
  init();
  sortHaystack();
  var t = timer('binarySearch benchmark');
  var firstIndex = 0;
  var lastIndex = haystack.length-1;
  var input = this.event.target.value;

  //currently point in the half of the array
  var currentIndex = (haystack.length-1)/2 | 0;
  var iterations = 0;

  while (firstIndex <= lastIndex) {
    currentIndex = (firstIndex + lastIndex)/2 | 0;
    iterations++;
    if (haystack[currentIndex]  < input) {
      firstIndex = currentIndex + 1;
      //console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
    } else if (haystack[currentIndex] > input) {
      lastIndex = currentIndex - 1;
      //console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
    } else {
      document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return true;
    }
  }
}

Answer 42

From (source) one can read:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. (..) In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Big O notation does not represent a function per si but rather a set of functions with a certain asymptotic upper-bound; as one can read from source:

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

Informally, in computer-science time-complexity and space-complexity theories, one can think of the Big O notation as a categorization of algorithms with a certain worst-case scenario concerning time and space, respectively. For instance, O(n):

An algorithm is said to take linear time/space, or O(n) time/space, if its time/space complexity is O(n). Informally, this means that the running time/space increases at most linearly with the size of the input (source).

and O(n log n) as:

An algorithm is said to run in quasilinear time/space if T(n) = O(n log^k n) for some positive constant k; linearithmic time/space is the case k = 1 (source).

Nonetheless, typically such relaxed phrasing is normally used to quantify (for the worst-case scenario) how a set of algorithms behaves compared with another set of algorithms regarding the increase of their input sizes. To compare two classes of algorithms (e.g., O(n log n) and O(n)) one should analyze how both classes of algorithms behaves with the increase of their input size (i.e., n) for the worse-case scenario; analyzing n when it tends to the infinity

In the image above big-O denote one of the asymptotically least upper-bounds of the plotted functions, and does not refer to the sets O(f(n)).

For instance comparing O(n log n) vs. O(n) as one can see in the image after a certain input, O(n log n) (green line) grows faster than O(n) (yellow line). That is why (for the worst-case) O(n) is more desirable than O(n log n) because one can increase the input size, and the growth rate will increase slower with the former than with the latter.

Answer 43

Just to express a complexity of an algorithm in a fast and simple way. The big O notation exist to explain the best, worst, and average-case time complexities for any given algorithm. There are just numerical functions over the size of possible problem instances.

In other way it is very difficult to work precisely with these functions, because they tend to:

• Have too many bumps – An algorithm such as binary search typically runs a bit faster for arrays of size exactly n = 2k − 1 (where k is an integer), because the array partitions work out nicely. This detail is not particularly significant, but it warns us that the exact time complexity function for any algorithm is liable to be very complicated, with little up and down bumps as shown in Figure 2.2.
• Require too much detail to specify precisely – Counting the exact number of RAM instructions executed in the worst case requires the algorithm be specified to the detail of a complete computer program. Further, the precise answer depends upon uninteresting coding details (e.g., did he use a case statement or nested ifs?). Performing a precise worst-case analysis like T(n) = 12754n2 + 4353n + 834lg2 n + 13546 would clearly be very difficult work, but provides us little extra information than the observation that “the time grows quadratically with n.”</li>

It proves to be much easier to talk in terms of simple upper and lower bounds of time-complexity functions using the Big Oh notation. The Big Oh simplifies our analysis by ignoring levels of detail that do not impact our comparison of algorithms. The Big Oh notation ignores the difference between multiplicative constants. The functions f(n)=2n and g(n) = n are identical in Big Oh analysis

https://mimoza.marmara.edu.tr/~msakalli/cse706_12/SkienaTheAlgorithmDesignMan ual.pdf