big o - time complexity of the following algorithm -

suppose node (in bst) defined follows (ignore setters/getters/inits).

class node {       node parent;      node leftchild;      node rightchild;      int value;      // ... other stuff } 

given reference node in bst (called startnode) , node (called target), 1 check whether tree containing startnode has node value equal target.value.

i have 2 algorithms this:

algorithm #1:

- `startnode`, trace way root node (using `node.parent` reference) : o(n) - root node, regular binary search target : o(log(n)) 

t(n) = o(log(n) + n)

algorithm #2: perform dfs (psuedo-code only)

current_node = startnode while root has not been reached        go 1 level current_node      perform binary-search node downward (excluding branch go up) 

what time-complexity of algorithm?

the naive answer o(n * log(n)), n while loop, there @ n nodes, , log(n) binary-search. obviously, way-overestimating!

the best (partial) answer come was:

• suppose each sub-branch has m_i nodes , there k sub-branches. in other words, k number of nodes between startnode , root node

• the total time be

.

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

(this best estimation forgot of maths better!)

---

so have 2 questions:

0) time-complexity of algorithm #2 in terms of n 1) algorithm better in term of time-complexity? 

ok, after digging through old maths books, able find upper bound of product of k numbers sum n p <= (n /k) ^k.

with said, t(n) function become:

t(n) = o(f(n, k)) f(n, k) = log((n/k)^k)      = k * log(n/k)      = k * log(n) - k * log(k) 

(remember, k number nodes between startnode , root, while n total number of node)

how go here? (ie., how simplify f(n, k)? or enough big-o analysis? )