1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Another log(n) algorithm

  1. Apr 3, 2016 #1
    1. The problem statement, all variables and given/known data
    Consider a complete binary tree T with n nodes (n = 2^d − 1 for some d). Each node v of T is labeled with a distinct real number x. Define a node v of T to be a local minimum if the label x is less than the label y for all nodes m that are joined to v by an edge. You are given such a complete binary tree T, but the labeling is only specified in the following implicit way: for each node v, you can determine the value x by probing the node. Show how to find a local minimum of T using only O(log n) probes to the nodes of T.

    2. Relevant equations

    3. The attempt at a solution
    The way how I attempted to do this problem was by recursively finding the local minimum in the left and right subtree and then compare those 2 with the root.
    Code (Text):

    int T(Root)
        int small_left;
        int small_right;
                 return root->data;
        if(root->data<small_left && root ->data<small_right)
            return root->data
        else if(small_left<small_right)
          return small_left;
       return small_right;
    Last edited: Apr 3, 2016
  2. jcsd
  3. Apr 4, 2016 #2


    User Avatar
    2017 Award

    Staff: Mentor

    Same problem as in the other thread, you go through the whole tree which needs O(n).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted