[big-o] What is the difference between T(n) and O(n)?

Using limits

Let's consider f(n) > 0 and g(n) > 0 for all n. It's ok to consider this, because the fastest real algorithm has at least one operation and completes its execution after the start. This will simplify the calculus, because we can use the value (f(n)) instead of the absolute value (|f(n)|).

  1. f(n) = O(g(n))

    General:

              f(n)     
    0 = lim -------- < 8
        n?8   g(n)
    

    For g(n) = n:

              f(n)     
    0 = lim -------- < 8
        n?8    n
    

    Examples:

        Expression               Value of the limit
    ------------------------------------------------
    n        = O(n)                      1
    1/2*n    = O(n)                     1/2
    2*n      = O(n)                      2
    n+log(n) = O(n)                      1
    n        = O(n*log(n))               0
    n        = O(n²)                     0
    n        = O(nn)                     0
    

    Counterexamples:

        Expression                Value of the limit
    -------------------------------------------------
    n        ? O(log(n))                 8
    1/2*n    ? O(sqrt(n))                8
    2*n      ? O(1)                      8
    n+log(n) ? O(log(n))                 8
    
  2. f(n) = T(g(n))

    General:

              f(n)     
    0 < lim -------- < 8
        n?8   g(n)
    

    For g(n) = n:

              f(n)     
    0 < lim -------- < 8
        n?8    n
    

    Examples:

        Expression               Value of the limit
    ------------------------------------------------
    n        = T(n)                      1
    1/2*n    = T(n)                     1/2
    2*n      = T(n)                      2
    n+log(n) = T(n)                      1
    

    Counterexamples:

        Expression                Value of the limit
    -------------------------------------------------
    n        ? T(log(n))                 8
    1/2*n    ? T(sqrt(n))                8
    2*n      ? T(1)                      8
    n+log(n) ? T(log(n))                 8
    n        ? T(n*log(n))               0
    n        ? T(n²)                     0
    n        ? T(nn)                     0
    

Examples related to big-o

Differences between time complexity and space complexity? Determining complexity for recursive functions (Big O notation) What exactly does big ? notation represent? How to merge two sorted arrays into a sorted array? Time complexity of Euclid's Algorithm Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)? Append an object to a list in R in amortized constant time, O(1)? What does O(log n) mean exactly? Is log(n!) = T(n·log(n))? Difference between Big-O and Little-O Notation

Examples related to time-complexity

Find common substring between two strings Why is the time complexity of both DFS and BFS O( V + E ) How to find time complexity of an algorithm Hash table runtime complexity (insert, search and delete) matrix multiplication algorithm time complexity how to calculate binary search complexity What are the time complexities of various data structures? Complexities of binary tree traversals Time complexity of Euclid's Algorithm What does O(log n) mean exactly?

Examples related to notation

What exactly does big ? notation represent? What do numbers using 0x notation mean? What exactly does += do in python? conversion from infix to prefix What does %w(array) mean? What is the difference between T(n) and O(n)?

Examples related to big-theta

What exactly does big ? notation represent? What is the difference between T(n) and O(n)?