View Single Post
Old 10-03-2016, 04:15 PM
zyteka zyteka is offline
Junior Member
Join Date: Sep 2016
Posts: 1
Default Problem 2.14(a + c)

I am having some difficulties working through problem 2.14

For a, I understand that the number of dichotomies that H can implement at most K times the number of hypothesis that H_1 can implement, which can implement N^(dvc + 1). I'm not sure how to relate this to the dvc(H).

For c, I can prove the first half of the min function using part a. For the second part of the min function, ( 7(dvc + K) log2 (dvcK) ), I plugged the function into the inequality in b, and simplified to get:
(dk)^(7(dvc+K)) > 2K(7(dvc + K) log(dvc K))^d

I am not sure how to proceed from here, and no simplifications I can do from here seem get closer to solving the inequality.
Reply With Quote