O（log n）是什么意思？

我目前正在学习Big O Notation运行时间和分期次数。 我理解O（n）线性时间的概念，这意味着input的大小会按比例影响algorithm的增长…例如二次时间O（n ² ）等也是如此。甚至algorithm，例如置换生成器，具有O（n！）次，以阶乘增长。

例如，下面的函数是O（n），因为该algorithm与其inputn成比例增长：

f(int n) { int i; for (i = 0; i < n; ++i) printf("%d", i); } 

同样，如果有一个嵌套循环，时间将是O（n ² ）。

但究竟是O（log n） ？ 例如，说一个完整的二叉树的高度是O（log n）是什么意思？

我知道（也许不是很详细）什么对数，在这个意义上说：log ₁₀ 100 = 2，但我不明白如何识别对数时间的函数。

Answer 1

我无法理解如何用日志时间来识别一个函数。

对数运行时函数最常见的属性是：

• 下一个要执行某个动作的元素的select是几种可能性之一
• 只有一个需要select。

要么

• 执行动作的元素是n的数字

这就是为什么，例如，查找电话簿中的人是O（log n）。 你不需要检查电话簿中的每个人find正确的; 相反，您可以根据姓名的字母顺序来查看，然后在每个部分只需要查看每个部分的子集，然后再找出某个人的电话号码即可。

当然，更大的电话本还是会花费更长的时间，但不会像增加额外的大小那样快速增长。

---

我们可以扩展电话本例子来比较其他types的操作和它们的运行时间。 我们将假设我们的电话簿中包含具有独特名称和人员 （“白页”）的企业（“黄页”），这些企业可能没有唯一的名称。 一个电话号码最多分配给一个人或企业。 我们还将假设需要一段时间才能翻到一个特定的页面。

以下是我们可能在电话簿上执行的一些操作的运行时间，从最好到最差：

• O（1）（最坏的情况）：给定一个公司的名字和公司名称，find电话号码。

• O（1）（一般情况下）：给定一个人姓名的页面和他们的名字，find电话号码。

• O（log n）：给定一个人的姓名，通过在你尚未search的书的中途选取一个随机点来查找电话号码，然后检查该人的姓名是否在那一点。 然后在书的那部分人的名字所在的地方重复一遍。 （这是一个二进制search一个人的名字。）

• O（n）：查找所有电话号码包含数字“5”的人。

• O（n）：给定一个电话号码，find具有该号码的人或企业。

• O（n log n）：打印机的办公室里有混乱，我们的电话簿已经把所有的页面以随机的顺序插入。 通过查看每个页面上的名字，然后将该页面放在新的空白电话簿中的适当位置，修正订购方式，使其正确无误。

对于下面的例子，我们现在在打印机的办公室。 电话簿正在等待邮寄给每个居民或企业，并且每个电话簿上都有一个标签，用于识别应该邮寄到哪里。 每个人或企业都有一个电话簿。

• O（n log n）：我们要个性化电话簿，所以我们要find每个人或企业的名字在他们指定的副本，然后在书中圈出他们的名字，写一个简短的谢谢你的惠顾笔记。

• O（n ² ）：办公室发生错误，每个电话簿中的每个条目在电话号码末尾都有一个额外的“0”。 采取一些白，并删除每个零。

• O（n·n！）：我们准备将电话本加载到发货docker上。 不幸的是，应该装载书籍的机器人已经不合时宜了，它将随机地将书放到卡车上！ 更糟糕的是，它把所有的书放到卡车上，然后检查是否按正确的顺序，如果没有，就卸载它们并重新开始。 （这是可怕的bogosorting 。）

• O（n ⁿ ）：你修理机器人，以便正确加载东西。 第二天，你的一个同事在你身上扮演一个恶作剧，将装卸docker机器人连接到自动打印系统。 每当机器人装入一本原始书籍，工厂的打印机就会重复运行所有的电话簿！ 幸运的是，机器人的缺陷检测系统已经足够成熟，机器人在遇到重复的书籍加载时不会尝试打印更多的副本，但是它仍然需要加载已打印的所有原始和重复的书籍。

Answer 2

这个问题已经有很多好的答案，但是我相信我们确实缺less了一个重要的答案，即所说的答案。

说一个完整的二叉树的高度是O（log n）是什么意思？

下图描绘了一个二叉树。 请注意，与上面的级别（因此是二进制 ）相比，每个级别包含节点数量的两倍：

二进制search就是一个复杂度为O(log n)的例子。 假设图1中树的最底层的节点表示一些sorting集合中的项目。 二进制search是一个分而治之的algorithm，图中显示了我们需要（最多）4个比较来find我们在这个16个数据集中search的logging。

假设我们有一个32个元素的数据集。 继续上面的绘图，发现我们现在需要5次比较来find我们正在search的内容，因为当我们乘以数据量时，树只有更深的一层。 因此，algorithm的复杂性可以描述为对数秩序。

在一张普通的纸上绘制log(n)将会得到一个曲线图，曲线的上升随着n增加而减速：

Answer 3

O(log N)基本上意味着时间线性上升，而n则呈指数增长。 因此，如果计算10元素需要2秒，则计算100元素需要2秒，计算100元素需要3秒，依此类推。

当我们分而治之时，例如二进制search就是O(log n) 。 另一个例子是快速sorting，每次我们将数组分成两部分，每次需要O(N)时间来find一个元素。 因此它NO(log N)

Answer 4

下面的解释是使用完全平衡二叉树的情况来帮助你理解我们如何得到对数时间复杂度。

二叉树就是一个大小为n的问题被分成大小为n / 2的子问题直到我们遇到大小为1的问题的情况：

这就是你如何得到O（log n），这是在上面的树上需要完成的工作量来达到一个解决scheme。

具有O（log n）时间复杂度的常见algorithm是二进制search，其recursion关系是T（n / 2）+ O（1），即在树的每个后续级别将问题分成一半，并执行额外的工作。

Answer 5

如果你有一个function，需要：

 1 millisecond to complete if you have 2 elements. 2 milliseconds to complete if you have 4 elements. 3 milliseconds to complete if you have 8 elements. 4 milliseconds to complete if you have 16 elements. ... n milliseconds to complete if you have 2**n elements. 

然后它需要log ₂ （n）的时间。 大O符号 ，松散地说，意味着这个关系只对大n有效，常数因子和小项可以忽略。

Answer 6

对数运行时间（ O(log n) ）本质上意味着运行时间与input大小的对数成比例地增长 – 例如，如果10个项目最多花费一些时间量x ，并且最多100个项目花费，比如说2x和10000个项目至多需要4x ，那么看起来就像O(log n)时间复杂度。

Answer 7

概观

其他人已经给出了很好的图例，比如树图。 我没有看到任何简单的代码示例。 所以除了我的解释，我还会提供一些简单的打印语句的algorithm来说明不同algorithm类别的复杂性。

首先，你需要有一个对数的总体思路，你可以从https://en.wikipedia.org/wiki/Logarithm获得。; 自然科学使用e和自然日志。 工程门徒将使用log_10（以10为底），而计算机科学家将使用log_2（以2为底数），因为计算机是基于二进制的。 有时您会看到自然对数的缩写为ln() ，工程师通常会将_10closures，只需使用log() ，log_2简写为lg() 。 所有types的对数都以相似的方式增长，这就是为什么它们共享相同的log(n)类别。

当你看下面的代码示例时，我build议查看O（1），然后O（n），然后O（n ^ 2）。 当你和这些人做好之后，再看看别人。 我已经包括干净的例子，以及变化，以演示如何微妙的变化仍然可以导致相同的分类。

你可以把O（1），O（n），O（logn）等等看作增长的类或类别。 有些类别比其他类别需要更多时间来完成。 这些类别帮助我们提供了一种sortingalgorithm性能的方法。 随着inputn的增长，一些增长得更快。 下表显示了数字上的增长。 在下表中，将log（n）视为log_2的上限。

各种大O类别的简单代码示例：

O（1） – 常数时间示例：

• algorithm1：

algorithm1打印hello一次，它不依赖于n，所以它总是运行在恒定的时间，所以它是O(1) 。

 print "hello"; 

• algorithm2：

algorithm2打印3次，但不取决于input大小。 即使n增长，这个algorithm总是只打印3次。 这就是说3，是一个常数，所以这个algorithm也是O(1) 。

 print "hello"; print "hello"; print "hello"; 

O（log（n）） – 对数例子：

• algorithm3 – 这就像“log_2”

algorithm3演示在log_2（n）中运行的algorithm。 注意for循环的post操作将i的当前值乘以2，所以i从1到2到4到8到16到32 …

 for(int i = 1; i <= n; i = i * 2) print "hello"; 

• algorithm4 – 这就像“log_3”

algorithm4演示log_3。 注意i从1到3到9到27 …

 for(int i = 1; i <= n; i = i * 3) print "hello"; 

• algorithm5 – 这就像“log_1.02”

algorithm5很重要，因为它有助于表明，只要数字大于1，并且结果反复地与自身相乘，那么您正在查看对数algorithm。

 for(double i = 1; i < n; i = i * 1.02) print "hello"; 

O（n） – 线性时间示例：

• algorithm6

这个algorithm很简单，打印出你好n次。

 for(int i = 0; i < n; i++) print "hello"; 

• algorithm7

这个algorithm显示了一个变化，它会打印你好n / 2次。 n / 2 = 1/2 * n。 我们忽略1/2常数并且看到这个algorithm是O（n）。

 for(int i = 0; i < n; i = i + 2) print "hello"; 

O（n * log（n）） – nlog（n）例子：

• algorithm8

把它看作O(log(n))和O(n) 。 for循环的嵌套帮助我们获得O(n*log(n))

 for(int i = 0; i < n; i++) for(int j = 1; j < n; j = j * 2) print "hello"; 

• algorithm9

algorithm9与algorithm8类似，但是每个循环都允许变化，这仍然导致最终结果为O(n*log(n))

 for(int i = 0; i < n; i = i + 2) for(int j = 1; j < n; j = j * 3) print "hello"; 

O（n ^ 2） – n平方例子：

• algorithm10

O(n^2)很容易通过嵌套标准for循环获得。

 for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) print "hello"; 

• algorithm11

像algorithm10，但有一些变化。

 for(int i = 0; i < n; i++) for(int j = 0; j < n; j = j + 2) print "hello"; 

O（n ^ 3） – n cubed例子：

• algorithm12

这就像algorithm10，但有3个循环，而不是2个。

 for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) for(int k = 0; k < n; k++) print "hello"; 

• algorithm13

像algorithm12，但有一些变化仍然产生O(n^3) 。

 for(int i = 0; i < n; i++) for(int j = 0; j < n + 5; j = j + 2) for(int k = 0; k < n; k = k + 3) print "hello"; 

概要

以上提供了几个直接的例子和变化，以帮助certificate可以引入什么微妙的变化，真正不改变分析。 希望它给你足够的洞察力。

Answer 8

你可以直观地看O（log N），说时间与N中的位数成正比。

如果一个操作对input的每个数字或位执行恒定的时间工作，则整个操作将花费与input中的位数或位数成正比的时间，而不是input的大小; 因此，O（log N）而不是O（N）。

如果一个操作做出一系列恒定的时间决定，其中每一个都减半（减less3,4,5倍）input的大小，整个将花费与时间基准2成比例的时间（基数3 ，基数4，基数5 …），而不是O（N）。

等等。

Answer 9

我一直不得不精神可视化运行在O（log n）中的algorithm的最佳方式如下：

如果你通过乘数增加问题的大小（即把它的大小乘以10），工作只会增加一个额外的量。

把它应用到你的二叉树问题中，所以你有一个很好的应用：如果你把二叉树中的节点数加倍，那么高度只会增加1（一个添加量）。 如果你再加倍，它仍然只增加1（显然我假设它保持平衡等）。 这样一来，当问题规模倍增时，不是将工作翻倍，而只是做更多的工作。 这就是O（log n）algorithm真棒的原因。

Answer 10

对数

好吧，让我们试着完全理解一个对数究竟是什么。

想象一下，我们有一根绳子，我们已经把它绑在一匹马上。 如果绳子直接绑在马上，那么这匹马需要拉开的力量（比如从一个男人身上）就是1。

现在想象一下绳子绕在一根杆子上。 要逃跑的马现在不得不拉多次。 时间的长短取决于绳子的粗糙程度和杆子的大小，但是我们假设它会把自己的力量乘以10（当绳子完成转弯时）。

现在，如果绳子缠绕一圈，那么这匹马将需要拉动十倍。 如果人决定让这匹马非常困难，他可能会再次将绳子缠绕在一根杆子上，增加10倍的力量。 第三个回合会再次增加10倍的力量。

我们可以看到，对于每一个循环，价值增加10。获得任何数字所需的匝数被称为数字的对数，即我们需要3个职位，你的实力倍增1000倍，6个职位，乘以你的实力1,000,000。

3是1,000的对数，6是1000000的对数（基数10）。

那么O（log n）究竟是什么意思呢？

在我们上面的例子中，我们的“增长率”是O（log n） 。 对于每一个额外的循环，我们的绳索可以处理的力量是以上的10倍：

 Turns | Max Force 0 | 1 1 | 10 2 | 100 3 | 1000 4 | 10000 n | 10^n 

现在上面的例子确实使用了基数10，但幸运的是，当我们谈论大的符号时，日志的基数是微不足道的。

现在让我们想象你正在猜测1-100之间的数字。

 Your Friend: Guess my number between 1-100! Your Guess: 50 Your Friend: Lower! Your Guess: 25 Your Friend: Lower! Your Guess: 13 Your Friend: Higher! Your Guess: 19 Your Friend: Higher! Your Friend: 22 Your Guess: Lower! Your Guess: 20 Your Friend: Higher! Your Guess: 21 Your Friend: YOU GOT IT! 

现在，你花了7猜，得到这个权利。 但是这里有什么关系？ 从每个额外的猜测中可以猜出的项目数量是多less？

 Guesses | Items 1 | 2 2 | 4 3 | 8 4 | 16 5 | 32 6 | 64 7 | 128 10 | 1024 

使用图表，我们可以看到，如果我们使用二进制search来猜测1-100之间的数字，那么最多只需要 7次尝试。 如果我们有128个数字，我们也可以在7次尝试中猜出数字，但是129个数字最多需要 8次尝试（在与对数的关系中，这里我们需要对128个值范围进行7次猜测，对1024个值范围进行10次猜测7是128的对数，10是1024的对数（基数2））。

请注意，我最多是粗体的。 大o符号总是指最差的情况。 如果你幸运的话，你可以一次猜出这个数字，所以最好的情况是O（1），但这是另一回事。

我们可以看到，对于每一个猜测我们的数据集正在缩小。 确定algorithm是否具有对数时间的一个很好的经验法则是查看数据集在每次迭代之后是否缩小一定的顺序

O（n log n）呢？

你最终会遇到一个线性时间O（n log（n）algorithm，上面的经验法则再次适用，但是这次对数函数必须运行n次，例如减less列表的大小n次像一个mergesort。

您可以轻松识别algorithm时间是否为n log n。 寻找遍历列表（O（n））的外部循环。 然后看看是否有一个内部循环。 如果内部循环切割/减less每次迭代的数据集，则该循环为（O（log n），所以整体algorithm为= O（n log n） 。

免责声明：绳索对数的例子是从W.Sawyer的优秀math家的Delight书中抓取的 。

Answer 11

什么是日志_b （n）？

这是在达到大小为1的部分之前，可以将长度为n的logging反复切割成相等部分的次数。

Answer 12

分而治之algorithm通常对运行时间有一个logn分量。 这是来自input的重复减半。

在二分search的情况下，每次迭代都会丢掉一半的input。 应该注意的是，在Big-O表示法中，日志是以2为底数的。

编辑：如前所述，日志基地并不重要，但是当推导出一个algorithm的Big-Operformance时，对数因子将会减半，所以我认为它是基数2。

Answer 13

但究竟是O（log n）？ 例如，说一个>完整的二叉树的高度是O（log n）是什么意思？

我会把这个改为“完整的二叉树的高度是log n”。 如果你正在一步一步遍历下来，那么确定一个完整的二叉树的高度就是O（log n）。

我无法理解如何用对数时间来识别函数。

对数本质上是指数的倒数。 所以，如果你的函数的每个“步骤”都是从原始项集合中消除一个元素的因子 ，那么这是一个对数时间algorithm。

对于树例子，您可以很容易地看到，在继续遍历时，降低节点级别会削减指数数量的元素。 查看通过名称sorting的电话簿的stream行示例基本上等同于遍历二叉search树（中间页面是根元素，并且可以在每个步骤中推导出是向左还是向右）。

Answer 14

O(log n)是指与对数成比例的时间量的函数（或者algorithm，或者algorithm中的一个步骤）（大多数情况下，通常是基数2，但并不总是，在任何情况下，这都是不显着的-O符号*）的input大小。

对数函数是指数函数的倒数。 换一种说法，如果您的input按照指数增长（而不是像通常那样线性增长），则函数会线性增长。

O(log n)运行时间在任何一种分而治之的应用程序中是非常普遍的，因为你（理想上）每次裁减一半的工作。 如果在每一个分割或者征服的步骤中，你在做恒定的时间工作（或者工作不是恒定的，但是时间比O(log n)慢得多），那么你的整个函数是O(log n) 。 每个步骤在input上需要线性时间是相当常见的; 这将相当于O(n log n)的总时间复杂度。

二进制search的运行时间复杂度是O(log n)一个例子。 这是因为在二进制search中，在每个后面的步骤中，总是忽略一半的input，将数组分成两半，每一步只关注一半。 每一步都是恒定的，因为在二进制search中，只需要比较一个元素和你的键值，就可以知道下一步该做什么，无论你考虑的数组有多大。 所以你做了大约log（n）/ log（2）的步骤。

合并sorting的运行时间复杂度是O(n log n)一个例子。 这是因为您将每个步骤的数组分成两半，导致总共大约log（n）/ log（2）个步骤。 但是，在每一步中，您需要对所有元素执行合并操作（无论是n / 2元素的两个子列表中的一个合并操作还是n / 4元素的四个子列表上的两个合并操作）是无关紧要的，因为这增加了必须为每个步骤中的n个元素执行此操作）。 因此，总的复杂度是O(n log n) 。

*请记住，大O符号， 根据定义 ，常量并不重要。 同样由于对数的基本规则的变化，不同基数的对数之间的唯一差异是一个常数因子。

Answer 15

简而言之：在algorithm的每一步，您都可以将工作减半。 （渐近地相当于第三，第四，…）

Answer 16

It simply means that the time needed for this task grows with log(n) (example : 2s for n = 10, 4s for n = 100, …). Read the Wikipedia articles on Binary Search Algorithm and Big O Notation for more precisions.

Answer 17

If you plot a logarithmic function on a graphical calculator or something similar, you'll see that it rises really slowly — even more slowly than a linear function.

This is why algorithms with a logarithmic time complexity are highly sought after: even for really big n (let's say n = 10^8, for example), they perform more than acceptably.

Answer 18

These 2 cases will take O(log n) time

 case 1: f(int n) { int i; for (i = 1; i < n; i=i*2) printf("%d", i); } case 2 : f(int n) { int i; for (i = n; i>=1 ; i=i/2) printf("%d", i); } 

Answer 19

But what exactly is O(log n)

What it means precisely is "as n tends towards infinity , the time tends towards a*log(n) where a is a constant scaling factor".

Or actually, it doesn't quite mean that; more likely it means something like " time divided by a*log(n) tends towards 1 ".

"Tends towards" has the usual mathematical meaning from 'analysis': for example, that "if you pick any arbitrarily small non-zero constant k , then I can find a corresponding value X such that ((time/(a*log(n))) - 1) is less than k for all values of n greater than X ."

---

In lay terms, it means that the equation for time may have some other components: eg it may have some constant startup time; but these other components pale towards insignificance for large values of n, and the a*log(n) is the dominating term for large n.

Note that if the equation were, for example …

time(n) = a + b log(n) + c n + d n n

… then this would be O(n squared) because, no matter what the values of the constants a, b, c, and non-zero d, the d*n*n term would always dominate over the others for any sufficiently large value of n.

That's what bit O notation means: it means "what is the order of dominant term for any sufficiently large n".

Answer 20

I can add something interesting, that I read in book by Kormen and etc. a long time ago. Now, imagine a problem, where we have to find a solution in a problem space. This problem space should be finite.

Now, if you can prove, that at every iteration of your algorithm you cut off a fraction of this space, that is no less than some limit, this means that your algorithm is running in O(logN) time.

I should point out, that we are talking here about a relative fraction limit, not the absolute one. The binary search is a classical example. At each step we throw away 1/2 of the problem space. But binary search is not the only such example. Suppose, you proved somehow, that at each step you throw away at least 1/128 of problem space. That means, your program is still running at O(logN) time, although significantly slower than the binary search. This is a very good hint in analyzing of recursive algorithms. It often can be proved that at each step the recursion will not use several variants, and this leads to the cutoff of some fraction in problem space.

Answer 21

O(log n) is a bit misleading, more precisely it's O(log ₂ n), ie (logarithm with base 2).

The height of a balanced binary tree is O(log ₂ n), since every node has two (note the "two" as in log ₂ n) child nodes. So, a tree with n nodes has a height of log ₂ n.

Another example is binary search, which has a running time of O(log ₂ n) because at every step you divide the search space by 2.

Answer 22

First I recommend you to read following book;

Algorithms (4th Edition)

Here is some functions and their expected complexities. Numbers are indicating statement execution frequencies .

Following Big-O Complexity Chart also taken from bigocheatsheet

Lastly very simple showcase there is shows how it is calculated;

Anatomy of a program's statement execution frequencies.

Analyzing the running time of a program (example).

Answer 23

log x to base b = y is the inverse of b^y = x

If you have an M-ary tree of depth d and size n, then:

• traversing the whole tree ~ O(M^d) = O(n)

• Walking a single path in the tree ~ O(d) = O(log n to base M)

Answer 24

I can give an example for a for loop and maybe once grasped the concept maybe it will be simpler to understand in different contexts.

That means that in the loop the step grows exponentially. 例如

 for (i=1; i<=n; i=i*2) {;} 

The complexity in O-notation of this program is O(log(n)). Let's try to loop through it by hand (n being somewhere between 512 and 1023 (excluding 1024):

 step: 1 2 3 4 5 6 7 8 9 10 i: 1 2 4 8 16 32 64 128 256 512 

Although n is somewhere between 512 and 1023, only 10 iterations take place. This is because the step in the loop grows exponentially and thus takes only 10 iterations to reach the termination.

The logarithm of x (to the base of a) is the reverse function of a^x.

It is like saying that logarithm is the inverse of exponential.

Now try to see it that way, if exponential grows very fast then logarithm grows (inversely) very slow.

The difference between O(n) and O(log(n)) is huge, similar to the difference between O(n) and O(a^n) (a being a constant).

Answer 25

In information technology it means that:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, such that for all N>N0 "C*g(n) > f(n) > 0" is true. 

Ant it seems that this notation was mostly have taken from mathematics.

In this article there is a quote: DE Knuth, "BIG OMICRON AND BIG OMEGA AND BIG THETA", 1976 :

On the basis of the issues discussed here, I propose that members of SIGACT, and editors of computer science and mathematics journals, adopt notations as defined above, unless a better alternative can be found reasonably soon .

Today is 2016, but we use it still today.

---

In mathematical analysis it means that:

  lim (f(n)/g(n))=Constant; where n goes to +infinity 

But even in mathematical analysis sometimes this symbol was used in meaning "C*g(n) > f(n) > 0".

As I know from university the symbol was intoduced by German mathematician Landau (1877-1938)

Answer 26

The complete binary example is O(ln n) because the search looks like this:

 1 2 3 4 5 6 7 8 9 10 11 12 

Searching for 4 yields 3 hits: 6, 3 then 4. And log2 12 = 3, which is a good apporximate to how many hits where needed.

Answer 27

If you are looking for a intuition based answer I would like to put up two interpretations for you.

1. Imagine a very high hill with a very broad base as well. To reach the top of the hill there are two ways: one is a dedicated pathway going spirally around the hill reaching at the top, the other: small terrace like carvings cut out to provide a staircase. Now if the first way is reaching in linear time O(n), the second one is O(log n).

2. Imagine an algorithm, which accepts an integer, n as input and completes in time proportional to n then it is O(n) or theta(n) but if it runs in time proportion to the number of digits or the number of bits in the binary representation on number then the algorithm runs in O(log n) or theta(log n) time.

Answer 28

I would like to add that the height of the tree is the length of the longest path from the root to a leaf, and that the height of a node is the length of the longest path from that node to a leaf. The path means the number of nodes we encounter while traversing the tree between two nodes. In order to achieve O(log n) time complexity, the tree should be balanced, meaning that the difference of the height between the children of any node should be less than or equal to 1. Therefore, trees do not always guarantee a time complexity O(log n), unless they are balanced. Actually in some cases, the time complexity of searching in a tree can be O(n) in the worst case scenario.

You can take a look at the balance trees such as AVL tree . This one works on balancing the tree while inserting data in order to keep a time complexity of (log n) while searching in the tree.

Answer 29

Algorithms in the Divide and Conquer paradigm are of complexity O(logn). One example here, calculate your own power function,

 int power(int x, unsigned int y) { int temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp; } 

from http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/

Answer 30

Actually, if you have a list of n elements, and create a binary tree from that list (like in the divide and conquer algorithm), you will keep dividing by 2 until you reach lists of size 1 (the leaves).

At the first step, you divide by 2. You then have 2 lists (2^1), you divide each by 2, so you have 4 lists (2^2), you divide again, you have 8 lists (2^3)and so on until your list size is 1

That gives you the equation :

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(you take the lg of each side, lg being the log base 2)