1. Not finding help here? Sign up for a free 30min 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!

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;
            if(root!=null)
               if(root->left==null)
                 {
                 return root->data;
                 }
        small_left=T(root->left)
        small_right=T(root->right)
        if(root->data<small_left && root ->data<small_right)
            return root->data
        else if(small_left<small_right)
          return small_left;
        else
       return small_right;
    }
     
     
    Last edited: Apr 3, 2016
  2. jcsd
  3. Apr 4, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Same problem as in the other thread, you go through the whole tree which needs O(n).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Another log(n) algorithm
  1. Log(n) algorithm (Replies: 5)

Loading...