Gnarly

I have to analyse functions that deal with trees for my C++ class.

I understand the concept of of log, constant, linear, quadratic functions, and Big-O notation, but not so much when it comes to trees.

There are three functions, function 3 calls 2, 2 calls 1, and 1 prints out data. To traverse this tree (each node can have unlimited number of branches, but in this case they have 4), the 3rd function is called, nested in its for loop function 2 is called, nested in 2's for loop function 1 is called.

Loops 3 and 2 depend on the number of children while 3 depends on how many values are stored in each member. What is the big O notation for the functions?

I initially thought quadratic because of the nested loops, but logically it seems as the tree gets larger, it takes constant time to traverse it and print all of it's data out.

Your thoughts?

I can try to reword this if necessary.

Thanks,

Wyatt

(ps, I might have different questions later, so check back if these types of problems are fun for ya.)

TFL Replica

You need to reword the part where you explained the functions (and maybe post the code as well). What is function 2 doing?

There's no way it's constant though. A larger tree does not take the same time to traverse as a smaller one. That's before even taking into account the other 2 functions you have thus far only vaguely defined.

__________________