0

I guess it's rather simple but it seems I'm troubling myself..

what's the complexity of the following?

// let's say that Q has M initial items
while Q not empty
  v <- Q.getFirst

  for each z in v // here, every v cannot have more than 3 z's
    ...
    O(1) operations here
    ...
    Q.insert(z)
  end
end

The number of the times this will happen, depends on if at some point v's do not have more z's (let's call this number N)

Is the complexity O(MxN^2) or I'm wrong? It's like having a tree with M parent nodes and each node, at most, can have three children. N is the total number of nodes.

foxTox
  • 128
  • 1
  • 8
  • What is the complexity of your `Q.getFirst` and your `Q.insert(z)`? – Zim-Zam O'Pootertoot Mar 26 '17 at 17:41
  • well, it doesn't really matter if it's an array, queue or stack, so I would choose an array. O(1) for getFirst and O(n) for insert – foxTox Mar 26 '17 at 18:19
  • hm.. now that I reconsider, if you just put something in the end of the stack(insert) and just get something which is first, so to resemble a FIFO function, is the complexity considered O(1) or due to the e.g. c++ implementation which both are in an array is considered a O(n) complexity? – foxTox Mar 26 '17 at 18:30
  • 1
    The complexity would be considered amortized constant time: https://stackoverflow.com/questions/15079327/amortized-complexity-in-laymans-terms – Zim-Zam O'Pootertoot Mar 26 '17 at 19:17

1 Answers1

1

Your algorithmic complexity should have an upper bound of O( (M * v) - parent nodes that are children nodes ) which is much better stated as O(n) where n is the number of nodes in your tree, since you only iterate the tree once.

Depending on your operation, you would want to consider the runtime of your Q.insert(z) and Q.getFirst() operation, because depending on your data structure that may be worth considering.

Assuming Q.insert() and Q.getFirst() runtimes are O(1), you can say O(M * v) is an approximate bounding, but since v elements can be repeated, you are better off stating that the runtime is just O(n) because O(m*v) actually overestimates the upper bound in all cases. O(n) is exact for every instance of the tree (n being the number of nodes).

I would say that it's much more safe to call it O(n) since I don't know the exact implementation of your insert - although with a linked list both insert and the get first can be O(1) operations. (Most binary tree inserts will be O(log n) if properly implemented - sufficient information was not provided)

It should not harm you to play it safe and consider your runtime analysis O(n), but depending on who you're pitching it to, that extra variable may seem unnecessary.

HTH

edited: clarity of problem in comments helped me understand the question better, fixed nonsense

dddJewelsbbb
  • 626
  • 4
  • 17
  • thanks a lot for the detailed explanation. Actually is the other way around, M is considerably smaller than N. Also, something more: consider that you have a number of nodes N and you choose M of them to be the parent nodes of the aforementioned tree. So M is just a small fraction, usually of N (I don't know if M=1 or M=N is the worst case) – foxTox Mar 26 '17 at 18:23
  • If you're doing a singular tree traversal (going through the whole tree one node at a time) and you can shrink an O(1) implementation for both getFirst and insert (insert can be achieved via keeping a tail reference for a queue, as noted in your comments on your question) then the whole tree traversal should be O(n) complexity. This is assuming that you are attempting to add every node of the tree to a queue from root-to-child. Reading the pseudocode of your algorithm, I'm not exactly sure that /is/ what you're trying to do. I don't see recursive iteration of children. – dddJewelsbbb Mar 26 '17 at 18:52
  • well, for the pseudocode, z's are children of v's, which are inserted in the Q queue. About the complexity, indeed it's a singular tree traversal, but I didn't know if the multitude of M initial parent nodes changes the complexity so to have an O(MxN) or an O(N^2) or an O(MxN^2) – foxTox Mar 26 '17 at 19:10
  • But for each z, you assume that they are also a v after they are treated as a z, and their children are considered z's, then v's - correct? If so, the O(mv) is approximately equivalent to O(n) - but in the case of the singular tree traversal I would use O(n) as opposed to O(mv) because to get the exact approximation of the problem, it would be more like O(m*v - m's that are also v's) where M's are parents and v's are children. So, much safer to stick with O(n) – dddJewelsbbb Mar 26 '17 at 19:14
  • Essentially, if you only iterate every node as a "currently-being-looked-at" node only once, it's definitely O(n), where n is the number of nodes in your tree. – dddJewelsbbb Mar 26 '17 at 19:18
  • Glad to help. Have a great day :) – dddJewelsbbb Mar 26 '17 at 19:18