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)