Loading...

algogeeks@googlegroups.com

[Prev] Thread [Next]  |  [Prev] Date [Next]

[algogeeks] Re: google question Dave Mon Feb 27 21:00:39 2012

@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
where h is the height of the triangle of cups, but the number of cups
is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
yours.

You'll have to admit that my data structure, an array, is simpler than
your graph.

Dave

On Feb 27, 10:09 pm, atul anand <[EMAIL PROTECTED]> wrote:
> @Dave : my code is not that complicated ...if you ignore the helper
> function and check fillCup();
> it just similar to preorder travesal and pour half to left and right child.
>
> here is the explanation :-
>
> node* fillCup(node *root,float pour,float capacity)
> {
> float temp;
>     if(root==NULL)
>         return NULL;
>
>     if(root->data+pour >= capacity)
>     {
>         if(root->data==0) //  if cup is empty then fill cup to full and
> reduce pour value for the next level
>         {
>             root->data=capacity;
>             pour=pour-capacity;
>         }
>         else
>         {
>             // if there is alreday some water in the cup , then it will
> fill the cup and reduce pour =pour - empty volume in partially filled cup.
>             temp=capacity-(root->data);
>             root->data=capacity;
>             pour=pour-temp;
>             if(pour==0)
>             {
>                 return root;
>             }
>
>         }
>     }
>     else
>     {
>        // this is for the part where overflow will never happen , even
> after adding the poured quantity to the cup.
>         root->data+=pour;
>         return root;
>
>     }
>
>     fillCup(root->left,pour/2,capacity);    // pour 1/2 to the left
>     fillCup(root->right,pour/2,capacity); //  pour 1/2 to the right
>
> }
>
> Time complexity = O(n).
>
> your approach is nice but it O(n^2) .

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.