0

I am trying to calculate the runtime of a function I wrote in Javq, I wrote a function that calculates the sum of all the right children in a BT.

I used recursion in the function, and I don't really understand how to calculate the runtime in recursion non the less in a BT (just started studying the subject).

This is the code I wrote:

public int sumOfRightChildren(){
    return sumOfRightChildren(this.root);
}

private int sumOfRightChildren(Node root){
    if(root == null) //O(1)
        return 0;//O(1)
    int sum = 0;//O(1)
    if(root.right != null)//O(1)
        sum+=root.right.data;//O(1)
    sum += sumOfRightChildren(root.right); //worst case O(n) ?
    if(root.left != null)
    {
       sum += sumOfRightChildren(root.left);//worst case O(n)?
    }
    return  sum;
}

I tried writing down the runtimes I think it takes, but I don't think I am doing it right. If someone can help guide me I'd be very thankful.

I'm trying to calculate T(n).

Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
Yuval Zecharia
  • 11
  • 2
  • 1
    Does this answer your question? [How do I time a method's execution in Java?](https://stackoverflow.com/questions/180158/how-do-i-time-a-methods-execution-in-java) – Krystian G Aug 18 '21 at 18:46
  • 2
    Not really I'm trying to calculate T(n) mathematically. – Yuval Zecharia Aug 18 '21 at 18:50
  • How come does it not help you? You`ll get the execution time in nanoseconds and then you convert to regular seconds or whatever you need it in – Padua Aug 18 '21 at 18:52
  • I am trying to find the worst case runtime. Umm like in witch family of functions (n,n^2,nlogn,logn...) this function is in. Like in the first recursion call I made I want to know how to write it mathematically like: T(n) = T(n-1)+5 and figure out the worst case runtime. Not literality get the amount of time it took it to run. – Yuval Zecharia Aug 18 '21 at 18:54
  • In other words I'm trying to find the mathematical expression for the recursion call's in the function. – Yuval Zecharia Aug 18 '21 at 18:59

2 Answers2

1

Since you visit every node exactly once is easy to see the runtime cost is T(n) = n * K where n is the number of nodes in the Binary Tree and K is the expected function cost.

If you want to explicitly consider the cost of certain operations you may not be able to calculate it exactly (without having an input example). For example, calculating the number of times sum+=... is executed is not possible because it depends on the particular tree.

In this case the worst case is a full Binary Tree and, if it is n=1,2,... their depth:

  1. the complexity is O(2^n) (no matter the operations since all of them take O(1) as you have posted).
  2. the cost of sum+=root.right.data; is T(n) = 2^n - 1 (all internal nodes).
  3. the cost of sum+=... is T(n) = 3 * (2^n - 1) (twice for every internal node and one more for each node).
  4. ...

(NOTE: the exact final expression may vary since your if(root.left != null) is not usefull and prefereable let that condition to the if(root == null))

josejuan
  • 9,338
  • 24
  • 31
0

Ok I think I understood, The worst case is that is has to check all the nodes in the tree so the answer is: O(n)

Yuval Zecharia
  • 11
  • 2