Q:

Big O with recursion

My AP comp sic class just recently went over Big O in a few basic sorting algorithms. I am a bit confused though on how it works with recursion and when I went to other stack overflow answers, I wasn't quite sure how they were getting their multiples of n for each level of the recursive function and adding them into their final answer.
I wanted to find the Big-O notation for node.nodeSortTest(int[] someArray) in this class that I made up. 
How would I get to the answer and what would it be?
public class node{

    public int value;

    public node higher = null;
    public node lower = null;

    //Making it a public static object was just easier for the test
    public static int addIndex = 0;

    public node(int i){
        value = i;
    }

    public void addToNode(int i){
        if(i>=value)
            if(higher != null) higher.addToNode(i);
            else higher = new node(i);
        else
            if(lower != null) lower.addToNode(i);
            else lower = new node(i);   
    }

    public static void nodeSortTest(int[] nums){
        if(nums.length<2)
            return;
        node keyNode = new node(nums[0]);
        for(int i = 1; i < nums.length; i++)
            keyNode.addToNode(nums[i]);
        node.addIndex = 0;
        keyNode.addTo(nums);
    }

    public void addTo(int[] nums){
        if(lower != null) lower.addTo(nums);
        nums[addIndex] = value;
        addIndex++;
        if(higher != null) higher.addTo(nums);
    }
}

A:

I added some code to prompt for a value of n and to calculate the number of operations on an array of n random integers.  The tests seem to be consistent with the O(n log2n) theory:
import java.util.Random;
import java.util.Scanner;

public class Node{

    public int value;

    public Node higher = null;
    public Node lower = null;

    //Making it a public static object was just easier for the test
    public static int addIndex = 0;
    public static int numOps = 0;

    public Node(int i){
        value = i;
    }

    public void addToNode(int i){
        if(i>=value)
            if(higher != null) higher.addToNode(i);
            else higher = new Node(i);
        else
            if(lower != null) lower.addToNode(i);
            else lower = new Node(i);
        numOps++;
    }

    public static void nodeSortTest(int[] nums){
        if(nums.length<2)
            return;
        Node keyNode = new Node(nums[0]);
        for(int i = 1; i < nums.length; i++)
            keyNode.addToNode(nums[i]);
        Node.addIndex = 0;
        keyNode.addTo(nums);
    }

    public void addTo(int[] nums){
        if(lower != null) lower.addTo(nums);
        nums[addIndex] = value;
        addIndex++;
        if(higher != null) higher.addTo(nums);
        numOps++;
    }
    public static void main(String args[]) {
        Random r = new Random();
        System.out.print("Enter size of array: ");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        int [] arrayToSort = new int [n];
        for (int i=0; i < n; i++) {
            arrayToSort[i] = r.nextInt(100000);
        }
        for (int i: arrayToSort) {
            System.out.print(i+",");
        }
        System.out.println();
        nodeSortTest(arrayToSort);
        for (int i:arrayToSort) {
            System.out.print(i+",");
        }
        System.out.println();
        System.out.println("\n\n\nn=" + arrayToSort.length + ", numOps=" + numOps);
        double log2n = Math.log(n)/Math.log(2);
        System.out.println("\n\nValue of n=" + n + " times log2n=" + log2n + " = " + n*log2n);
        scan.close();
    }
}

