Data Structure & Algorithms

Time Complexity

Time Complexity measures the amount of time an algorithms takes to complete a function. We can simply think it as how many times the code snippet will be executed.

Common Complexity represented by Big O natation:

O(1): Constant Complexity

int n = 10000;
System.out.println("you input is " + n);
System.out.println("I got " + n);

O(log n): Logarithmic Complexity

for (int i = i; i < n; i = i * 2) {
    System.out.println("Hey, I am looking at " + i);
}

O(n): Linear Complexity

for (int i = 1; i <= n; i++) {
    System.out.println("Hey, I am looking at " + i);
}

O(n^2): N square Complexity

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        System.out.println("Hey, I am looking at " + i + " and " + j);
    }
}

O(n^3): N cubic Complexity

for example, iterate over a three-dimensional array.

O(2^n): Exponential Growth

int fib(int n) {
    if (n < 2) return n;
    return fib(n -1) + fib(n -2);
}

O(n!): Factorial

int factorial(int n) {
    if (n = 0) return 1;
    return n * factorial(n -1);
}

Space Complexity

Space Complexity measures the amount of memory an algorithms uses.

O(n): the length of one dimensional array.

---

1. 覃超的算法训练营 - 极客时间 覃超 ↩