Question 190858 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Why does this function with random arguments always hit the base case the same number of times?

I want to determine the time complexity of the below code 👇

function random(a){
    let i;
    let num=Math.floor((Math.random()*(a+1)))
    return num;
}

function fuc1(n){
    let i;
    if(n<=0){
        alert("condition false ")
        return 0;
    }else{
        i=random(n-1);
        console.log("thisn")
        return fuc1(i)+fuc1(n-1-i);
    }
}

fuc1(6)

I added that alert statement, in order to count how many times 0 is returned. This number of executions would be useful to determine the time complexity.

Although there is a random aspect involved, I notice that the alert("condition false ") always executes 7 times. I don’t understand this. Why is it always the same 7 even though the arguments to the recursive calls are randomly determined?

Tags:

2

Answers


  1. 0

    Your function basically sums up random numbers until it reaches 0

    function random(a){
    let i;
    let num=Math.floor((Math.random()*(a+1))) // Get random number in specific range (0 to a + 2 I think)
    return num; // Return new random number
}

function fuc1(n){
    let i;
    console.log("func1",n) // Log information

    if(n<=0){
        
        // If n is 0 or less alert that "condition is false" and return 0
        console.log("condition false "+n)
        alert("condition false "+n)
        return 0;
    }else{
        i=random(n-1); // Get random number from smaller range
        console.log("thisn")
        return fuc1(i)+fuc1(n-1-i); // Get sum of two random numbers
    }
}

fuc1(6) // Call function with argument 6
    Login or Signup to reply.
  2. 0

    The function creates a recursion tree where n=0 represents a leaf node in that tree (it is a base case of the recursion), and any other (unsigned integer) value for n represents an internal node in that recursion tree.

    An example:

               ___6___
          /       
       __4__       1 (4+1=5)
      /          / 
     1       2   0   0
    /      / 
   0   0   1   0
          / 
         0   0

    The shape of that tree could have been different, as it is determined by the random number generator, but the invariants are that:

    • it is always a full binary tree, i.e. every node has either 2 children or no children at all. This follows from the fact that there are either no recursive calls made (the if case) or two (the else case), never one isolated call.

    • the sum of the arguments in fuc1(i)+fuc1(n-1-i) is always n-1. So when we first execute with n=6 (which is the root node), the direct children of that node have values whose sum is 5. It could have been 0 and 5, 1 and 4, 2 and 3, …etc, but always summing up to 5.

    Number of internal nodes in recursion tree

    Now we can prove that the number n represents the number of internal nodes that the recursion tree will have.

    We can prove that by induction:

    We already established that 0 represents a leaf (the if condition), and so it is true that n represents the number of internal nodes, i.e. there are none.

    If we assume that the premise is true for all unsigned integers between 0 and n-1 (inclusive), let’s see what we can say about n:

    The two recursive calls have arguments that sum up to n-1. So using the inductive assumption we know that these two calls each produce a recursion tree with a number of internal nodes that is equal to the argument they get. By consequence the total number of internal nodes generated by the two calls together is equal to n-1. Add to that the root of the recursion tree, and we have n internal nodes.

    And so we have proved that n represents the number of internal nodes of the recursion tree.

    Full binary trees with n internal nodes have n+1 leaf nodes, and this is why you always get 7 cases where the if block is executed (and you see the alert that many times).

    Time Complexity

    If we remove the printing/alerting from your code, the time complexity is directly related to the total executions of the function, which corresponds to the number of nodes (internal and leaves) of the recursion tree. From the above proof we know that this recursion tree has 2n+1 nodes, and so the algorithm has a time complexity of O(n).

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search