tree structure search and update; what is big omega for depth x?

In a binary tree the search is log (x) and the update is x where x is teh depth of the tree. Is this correct? In tree like structure (tree structure) what is the maximum number of access for record update? is it x? why? what about the search? I need teh answer and also why? Thanks

Induction Problem with Fibonacci Numbers

See attached

Big O - algorithm comparison

Suppose program A takes (2^n)/1000 units of time and program B takes 1000(n^2) units. For what values of n does program A take less time than program B. I am really looking for a detailed explanation on this problem - to check my answer. Thanks.

Big O Problem

The following is a big-oh relationship: n^10 is O(3^n) Please give witnesses n0 and c that can be used to prove the relationship. Choose your witnesses to be minimal, in the sense that n0-1 and c are not witnesses, and if d < c, then n0 and d are not witnesses. As a side note to the problem -- it may not be clear what d represents. d represents any positive constant that any function T(n) is O(dT(n)), regardless of whether d is a large number or a very small fraction, as long as d > 0. Typically it is used in the context of showing that constant factors do not matter.

Big O Problem - Proof

Show that F(n) + g(n) is O(max(f(n),g(n))). Any detail is appreciated.