time complexity of the following algorithm

Question

Suppose a Node (in a BST) is defined as follows (ignore all the setters/getters/inits).

class Node
{

     Node parent;
     Node leftChild;
     Node rightChild;
     int value;
     // ... other stuff
}

Given some a reference to some Node in a BST (called startNode) and another Node (called target), one is to check whether the tree containing startNode has any node whose value is equal to target.value.

I have two algorithms to do this:

Algorithm #1:

- From `startNode`, trace the way to the root node (using the `Node.parent` reference) : O(n)
- From the root node, do a regular binary search for the target : O(log(n))

T(n) = O(log(n) + n)

Algorithm #2: Basically perform a DFS (Psuedo-code only)

current_node = startnode
While the root has not been reached  
     go up one level from the current_node
     perform a binary-search from this node downward (excluding the branch from which we just go up)

What is the time-complexity of this algorithm?

The naive answer would be O(n * log(n)), where n is for the while loop, as there are at most n nodes, and log(n) is for the binary-search. But obviously, that is way-overestimating!

The best (partial) answer I could come up with was:

Suppose each sub-branch has some m_i nodes and that there are k sub-branches. In other words, k is the number of nodes between startNode and the root node
The total time would be

.

T(n) = log(m1) + log(m2) + ... + log(mk)
     = log(m1 * m2 * ... * mk)
Where m1 + m2 + ... + mk = n (the total number of nodes in the tree)

(This is the best estimation I could get as I forgot most of my maths to do any better!)

So I have two questions:

0) What is the time-complexity of algorithm #2 in terms of n
1) Which algorithm does better in term of time-complexity?

One Two Three · Accepted Answer · 2013-05-18 21:53:39Z

1

Ok, after digging through my old Maths books, I was able to find that the upper bound of a product of k numbers whose sum is n is p <= (n /k) ^k.

With that said, the T(n) function would become:

T(n) = O(f(n, k))
Where
f(n, k) = log((n/k)^k)
     = k * log(n/k)
     = k * log(n) - k * log(k)

(Remember, k is the number nodes between the startNode and the root, while n is the total number of node)

How would I go from here? (ie., how do I simplify the f(n, k)? Or is that good enough for Big-O analysis? )

answered May 18, 2013 at 21:53

One Two Three

23.8k27 gold badges80 silver badges117 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

time complexity of the following algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related