I need to determine the complexity of the pseudocode I wrote
while root ≠ null
while hasChild(root)
push(parentTree) ← root
root ← pop(getChilds(root))
...
is parentTree isEmpty
root ← null
else
root ← pop(parentTree)
How can I know the number of execution (for each line) in a worst case scenario ?
I am not able to determine it, because I actually does not know the first two lines. After, it's easy, but I don't know the count for the two first lines...
It's a tree implementation using a stack, and root is the root node, as you see.
By the way, it's the first time I write pseudo code, so I am not sure i wrote it in a good way. If it's not correct, I can rewrite it.
prima facie analysis leads me to think the runtime is O(logn*logn)
Reasoning: Outer while loop executes at most clogn times (where c is a constant). This is due to the fact that it relies on the 'root' variable, which in turn relies on the 'pop parenttree' parent tree only gets populated with the 'original' root's grandchildren, iteratively. At most it will have all the children down one path in the tree. Its known that the length of a single path down a tree is logn
Inner while loop also executes at most d logn times (d is constant), if the ... does not execute in O(1) then it would execute in dlogn+X, and the overall runtime would be O(logn*(logn+X)), likely simplifying to O(Xlogn)
Assuming the is is an if, the if/else statements run in O(1)
Outer*Inner = O(clogn*dlogn)