-1

How would I go about solving this problem: Use big O notation to give the number of nodes that can be contained in a tree of depth n

I'm not looking for the exact answer or anything, Just how I would go about to work out the answer?

AbcAeffchen
  • 14,400
  • 15
  • 47
  • 66
user1300788
  • 181
  • 2
  • 17
  • First of all, which kind of tree? A binary tree? An N-tree? – cdbitesky Dec 09 '13 at 20:30
  • 1
    You need to specify how many children each node in the tree may have, otherwise the answer is infinite. – Henry Dec 09 '13 at 20:30
  • @Henry So if the answer is infinite, how would you answer that using the big O? You obviously couldn't give a full answer but what would you write to work something like that out – user1300788 Dec 09 '13 at 20:34
  • @user1300788 in the case of an infinite answer you can't. Big O gives kind of an upper limit (up to a constant factor), but in this case there is none. – Henry Dec 09 '13 at 20:39
  • @ᴋᴇʏsᴇʀ No, other way around - X^n. – Bernhard Barker Dec 09 '13 at 20:48
  • @Dukeling Ah, yes, of course :) See I told you I wasn't thinking. I meant depth. – keyser Dec 09 '13 at 20:48
  • When I first saw this question I thought it was common enough that it must be a duplicate, but after seeing all of the mistakes in answering it, I can't help but say bravo for asking such an innocuous, yet clearly non-obvious question. – Slater Victoroff Dec 09 '13 at 20:53
  • @SlaterTyranus Wrong answers don't imply a good question. In my opinion this question is unclear (the problem is underspecified) (which can certainly be one of the causes of the wrong answers). – Bernhard Barker Dec 09 '13 at 20:58
  • @Dukeling I didn't mean to directly imply that, I just felt that the discussion and clearing of misconceptions that happened in this question were greater than average, and it generally took me by surprise, which I felt deserving of a +1, I can imagine why others would feel differently. – Slater Victoroff Dec 09 '13 at 21:01

3 Answers3

3

This was already alluded to in another answer, but specifically there are two relevant quantities in determining the big-O notation for this problem.

  • The depth of the tree (n)
  • The average number of children that each node has (k)

It's already obvious that if the tree has an infinite depth, then there will be an infinite number of nodes. What big-O notation is really trying to capture here is the rate at which the number of nodes in the tree will grow to infinity.

Since each layer of the tree will have approximately k times the number of nodes in the previous layer. In the first layer let's say we have some number a nodes, in the second layer then we have k*a nodes, and in the third layer we have k*k*a nodes.

One important piece about complexity is that constants (like a) don't really matter in the grand scheme of things, since 2*infinity is still infinity. Therefore the relevant progression in the previous step through is:

1 -> k -> k*k ->...

The function seems to be of the form, from these few examples, of k^something, you said not to provide the answer, so I won't directly give the answer, but I think this answer puts your right on the doorstep of it.

Good luck!

Slater Victoroff
  • 21,376
  • 21
  • 85
  • 144
  • I'm just glad to be the only answer on this question without downvotes. – Slater Victoroff Dec 09 '13 at 20:55
  • @user1300788 if it is a binary tree (one in which there are exactly 2 children for each node), then yes. However, that wasn't specified in your question. Remember, if you found this helpful, don't forget to mark this as the accepted answer. – Slater Victoroff Dec 09 '13 at 21:03
  • if the tree depth was 2 just say, would the number of nodes that can be contained be 2(2^2) – user1300788 Dec 09 '13 at 21:03
  • @user1300788 Depending on exactly how depth is calculated, and how many root nodes you have, then yes the answer could certainly be 2(2^2), but you know your specific application better than I do. – Slater Victoroff Dec 09 '13 at 21:06
  • No, it will not be 2(2^2) :). It does not work that way with big-O – trungdinhtrong Dec 09 '13 at 21:06
  • @user1339255 That was number of nodes, not big-O notation. – Slater Victoroff Dec 09 '13 at 21:07
  • But isnt it clear that he is deriving it from the big-O notion? – trungdinhtrong Dec 09 '13 at 21:09
  • and if you have more than 1 root node it will be called a "forest". A tree should have one root node IMO – trungdinhtrong Dec 09 '13 at 21:10
  • @user1339255 Not sure, I'm not a mind-reader, so I can't say what possible thought processes led to that thought, but what OP said implied an understanding of the problem. And second point is a small point of terminology and I don't think it makes sense to stick someone of that when they're just trying to understand the basic concept. – Slater Victoroff Dec 09 '13 at 21:12
  • Actually it seems to me that OP does not understand the problem. And your answer might actually mislead him to think that he did understand it. So terminology here is probably important. I am not undermining you at all. Just trying to help the OP. Hopefully by reading through our comment he will know if he understood the problem – trungdinhtrong Dec 09 '13 at 21:14
0

First you must can find a function f(n) representing the number of nodes that can contain in a tree of depth n, then you derive big O from n.

http://en.wikipedia.org/wiki/Big_O_notation

A simple way to derive big O from f(n) is as follow, as noted in the above link:

  • If f(x) is a sum of several terms, the one with the largest growth rate is kept, and all others omitted.

  • If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) are omitted.

So if you found f(n) = 100 * 2^n + 100000000 * n^ 2 + 2000000000000000000000000

then big O will be O(2^n)

trungdinhtrong
  • 2,604
  • 2
  • 17
  • 26
0

You need to find function which represents the upper bound of number of nodes in tree of depth n. So you need to look at the case where every node has maximal available number of childs. In case of binary tree every node has to have 2 childs so just draw some binary tree's and look for scheme. Look at the function below:

f(n) = number of nodes in depth n
f(1) = 1
f(2) = 2
f(3) = 4
f(4) = 8
f(n) = 2 * f(n-1) = 2 * 2 * f(n-2) = 2 * 2 * 2 * f(n-3) = 2*2*2*2...*2*f(1)

(you multiply by two n-1 times ) 2^(n-1) * 1 = 2^(n-1)

So to get upper bound of nodes in binary tree of depth n you need to sum these values:

Sum of f(n) for n from [1, n] = Sum of 2^(n-1) where n is from 1 to n = 2^(N) - 1
  • it's summation closed formula which you can get from any math text book or derive with few "tricks" by hand

So the maximum number of nodes in binary tree is bounded by 2^(n) - 1 where n is depth of binary tree which means it's belong asomptically to O(2^n). (in big-Oh notation you drop every constant).

fex
  • 3,488
  • 5
  • 30
  • 46
  • Subtle but important point: Big O notation does not refer to an upper-bound, and if there were a maximum number of children of 10, it wouldn't mean that the complexity were 10^n. Imagine if in your tree there were only a single node that actually had two children. At that point your big-O notation explanation would clearly fail. – Slater Victoroff Dec 09 '13 at 21:05
  • @SlaterTyranus In this case, the way the question was phrased ("number of nodes that can be contained in a tree") implies that we are looking for an upper bound. – interjay Dec 09 '13 at 21:08
  • @interjay, but say for instance the constraint was on average number of children rather than maximum number of children. I'm not saying your answer is necessarily wrong, I'm saying it makes assumptions that can be misleading if not explicitly mentioned. – Slater Victoroff Dec 09 '13 at 21:10
  • 1
    @SlaterTyranus Actually big-O is an upper bound (by definition). For example, saying something that's `O(n)` is also `O(n^2)` is correct (which is exactly why teaching institutions, and everyone else, should avoid it - either they have to mark correct answers as incorrect, or one can just say just about everything is `O(n^n)`). For a tight bound, it would have to be big-omega. – Bernhard Barker Dec 09 '13 at 21:29