Confused about these asymptotic notation and its runtime

Question

public static Asymptotic f3_notation = Asymptotic.BIG_THETA;
public static Runtime f3_runtime = Runtime.LINEAR;
/* When f3 is first called, start will be 0 and end will be the length of the array - 1 */
public int f3(char[] array, int start, int end) {
    if (array.length <= 1 || end <= start){
        return 1;
    }

    int mid = start + ((end - start) / 2);

    return f3(array, start, mid) + f3(array, mid + 1, end);
}

public static Asymptotic f4_notation = Asymptotic.BIG_THETA;
public static Runtime f4_runtime = Runtime.LINEARITHMIC;
/* When f4 is first called, start will be 0 and end will be the length of the array - 1 */
public int f4(char[] array, int start, int end) {
    if (array.length <= 1 || end <= start) return 1;

    int counter = 0;

    for (int i = start; i < end; i++) {
        if (array[i] == 'a') counter++;
    }

    int mid = start + ((end - start) / 2);

    return counter + f4(array, start, mid) + f4(array, mid + 1, end);
}

So I have these two methods. What I don't understand is that both have recursion but why is the first one is linear and the second method is linearithmic? I was told that if there is division or multiplication, usually its runtime is log-n. Though the first method has the division, it still is considered as linear but the second is not.

The more I understand, the more it confuses me and makes me feel like I know nothing.

Answer 1

The formula for the first method is:

T(n) = 2T(n/2) + O(1)

So if you draw the corresponding tree for this formula you will see that the amount of work is proportional to number of nodes in the tree which is O(n). Also you could use Master Method to solve this.

But for the second it is:

T(n) = 2T(n/2) + O(n)

In fact, what happens here is that your tree will have (just like the first method) O(log n) levels, but here in each level you are spending O(n) time which will result in O(n log n) time complexity. Again, Master Theorem works for this. Note that in the first case, though your tree (for the formula) will have O(log n) levels but in each level you will spend time proportional to the number of nodes on that level, and not O(n).