Time and Space Complexity

Time complexity is the amount of time taken by an algorithm to run as a function of the length of its input. This is important cause:

• Resources are limited.
• Helps measure algorithms to make programs more efficient.

We are no calculating with a stopwatch. We're looking at how many operations did the CPU have to perform. Say for example:

We are running a function which takes a value 'N' and runs a loop 'N' times:

public static void runningLoop(int N){
    for(int i=0; i<N; i++){
        //ops
    }
}

Here, the loop is running N times which means Time Complexity is directly proportional to N.
Hence, we say the time complexity is O(N). We'll get to what O is.

Similarly,
Space complexity is the amount of time space by an algorithm to run as a function of the length of its input. Let's take examples.

Say #1:

int a = 1;
int b[5];

Here, since space is not variable but fixed => O(1)

Say #2:

int arr[] = new int[N];

Here, since space is variable => O(N)

Units of Complexity

1. Big O: Upper Bound
2. Theta θ: Average case
3. Omega Ω: Lower Bound

Say:
We have to find an element in an array:

| 1 | 2 | 3 | 4 | 5 |

Omega is lowest bound which is the best case scenario.
If the element we're looking for is the first in the array then thats the best case scenario:
Ω(1)

Big O is highest bound which is the worst case scenario.
If the element we're looking for is the last in the array then thats the worst case scenario:
O(n)

Theta is average bound which is the average case scenario.
If the element we're looking for is the center in the array then thats the average case scenario:
θ(n/2)

Big O Complexities

1. Constant Time: O(1)

When only one operation is performed no matter what.
Doesn't grow with N.
Say for example:

int[] arr = {10, 20, 30, 40, 50};
System.out.println(arr[0]);

or

int sum = 10 + 20;

Regardless of what we do, whether the array contains 5 elements or 5 million elements, since we are accessing arr[0] that's one operation. Similarly, when adding two elements we are performing one operation. This makes the complexity O(1).

2. Linear Time: O(N)

When the number of operations increase with the value of N.
Grows ∝ N
Say for example:

for (int i = 0; i < n; i++) {
    System.out.println(arr[i]);
}

If:

• n=5 ~ Loop runs 5 times
• n=100 ~ Loop runs 100 times
• n=10000 ~ Loop runs 10000 times

and so on. This makes the complexity O(N).

3. Logarithmic Time: O(logN)

When after operation, the next set of operations are cut by half (More understood in Binary Search).
Grows very slowly.
Say for examples:

We are searching for an element in array of sizes:

16: 8 → 4 → 2 → 1
32: 16 → 8 → 4 → 2 → 1
64: 32 → 16 → 8 → 4 → 2 → 1

4. Quadratic Time: O(N^2)

When the number of operations increase with the value of N and within these N operations you are performing a set of another N operations.
Say for example:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + " " + j);
    }
}

If:

• n=5 ~ Loop runs 25 times
• n=100 ~ Loop runs 10000 times
• n=10000 ~ Loop runs 100000000 times

and so on. This makes the complexity O(N^2).
It's pretty bad XD

5. Cubic Time: O(N^3)

Similar to O(N^2) but worser.

Simplifying Expressions

There 3 main rules to simplifying Big O complexities:

Rule 1: Ignore constants.

Examples:
O(5N) = O(N)
O(100000N) = O(N)
O(3N + 2) = O(N)

Rule 2: Ignore the smaller terms since we're looking for worst case scenario.

Examples:
O(N^2 + N) = O(N^2)
O(N^2 + n + 10) = O(N^2)
O(logN + N^3 + 100000N) = O(N^3)

Rule 3: Add sequential operations and Multiply nested operations.

// Sequential Ops
for (int i = 0; i < n; i++) {
    System.out.println(arr[i]);
}

for (int i = 0; i < n; i++) {
    System.out.println(arr[i]);
}

for (int i = 0; i < n; i++) {
    System.out.println(arr[i]);
}

// Complexity: O(N + N + N) = O(3N) = O(N)

// Nested Ops
for (int i = 0; i < n; i++) {
    for (int i = 0; i < n; i++) {
    System.out.println(arr[i]);
    }
}

// Complexity: O(N * N) = O(N^2)

Order of Preferred Complexities

O(1) > O(logN) > O(rootN) > O(N) > O(NlogN) > O(N^2) > O(N^3) > O(2^N) > O(N!) > O(N^N)
<--- LEAST COMPLEXITY HIGHEST COMPLEXITY ---->

Practice Questions

Question 1:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

Answer 1: O(n)

Question 2:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

for (int j = 0; j < n; j++) {
    System.out.println(j);
}

Answer 2: O(N+N)=O(2N) => O(N)

Question 3:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + " " + j);
    }
}

Answer 3: O(N^2)

Question 4:

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + j);
    }
}

Answer 4: O(n + n^2) = O(n^2)

Question 5:

for (int i = 1; i < n; i *= 2) {
    System.out.println(i);
}

Answer 5: O(logn)

Question 6:

for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j *= 2) {
        System.out.println(i + " " + j);
    }
}

Answer 6: O(nlogn)

Question 7:

for (int i = 1; i < n; i *= 2) {
    for (int j = 1; j < n; j *= 2) {
        System.out.println(i + " " + j);
    }
}

Answer 7: O(log^2 n)

Question 8:

for (int i = n; i > 0; i /= 2) {
    System.out.println(i);
}

Answer 8: O(logn)

Question 9:

for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j *= 2) {
        for (int k = 0; k < n; k++) {
            System.out.println(i + j + k);
        }
    }
}

Answer 9: O(n^2 logn)

Question 10:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        System.out.println(i + " " + j);
    }
}

Answer 10: O(n^2)