Sorting algorithms

Question 1

no comparison based algorithm can guarantee to search a sequence of n element for a particular value in better than O(log n) time

Answer 1

Any comparison algorithm can be represented by a decision tree with k nodes
branch nodes represent the comparisons performed
leaf nodes are the outcomes of the search

the number of branch nodes is at least n，since the search must allow for the item searched for being equal to any one of the items in the given sequence.
hence since the branch nodes size of binary tree size k is k/2 ,
we have k/2 >= n -> k >= 2n
if height of tree = h

2^h >= 2n -> 2^h >= 2n

             - > log2 (2^h) >= log2 (2n)
             - > h log2 2 >= log2 2 + log2 n 
             - > h >= 1 + log2 n

since the worst case comparison = height of tree

worst case >= 1 + log 2 n