What does the notation T(n) mean?

Question

We learned about big O notation, but I often see T(n) as well. For example,

public static Comparable[] mergeSort(Comparable[] A, int low, int high) {
  if (low < high) { //at least 2 elements?                //cost = c
    int mid = (low + high)/2;                             //cost = d
    Comparable[] A1 = mergeSort(A, low, mid);             //cost = T(n/2) + e
    Comparable[] A2 = mergeSort(A, mid+1, high);          //cost = T(n/2) + f
    return merge(A1,A2);                                  //cost = g n + h
  }
  .... //cost = i

I believe c,d,e,... are meant to be arbitrarily named constants.

What does T(n/2) mean? also how is T notation related to big O?

Answer 1

This notation refers to the maximum amount of time (or, more specifically, steps) that a function takes to run.

T(n) may be much more specific than O(n); for example, let's say you have a program that for any input, requires n^2+n+1 steps to run:

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

More information can be found here.