# Java Time Complexity and Space Complexity

Time Complexity and Space Complexity are important concepts in **Data Structures and Algorithms (DSA)**. They help us understand how efficient a Java program or algorithm is.

**1\. What is Time Complexity?**

**Definition:** Time Complexity describes how the execution time of an algorithm grows as the input size `n` increases.

It is usually represented using **Big O notation**.

**Example:**

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

The loop runs `n` times.

```text
Time Complexity: O(n)
```

* * *

**2\. What is Space Complexity?**

**Definition:** Space Complexity describes how much additional memory an algorithm needs as the input size increases.

**Example:**

```java
int[] arr = new int[n];
```

The array requires memory proportional to `n`.

```text
Space Complexity: O(n)
```

* * *

**Big O Notation**

Big O describes the **upper-bound growth rate** of an algorithm.

Common complexities:

```text
O(1)        → Constant
O(log n)    → Logarithmic
O(n)        → Linear
O(n log n)  → Linearithmic
O(n²)       → Quadratic
O(n³)       → Cubic
O(2ⁿ)       → Exponential
O(n!)       → Factorial
```

* * *

**3\. O(1) — Constant Time**

The execution time does not depend on the input size.

**Example:**

```java
int first = arr[0];
```

```text
Time Complexity: O(1)
```

* * *

**4\. O(log n) — Logarithmic Time**

The input is reduced significantly during each operation.

**Example:**

```text
Binary Search
```

```text
Time Complexity: O(log n)
```

* * *

**5\. O(n) — Linear Time**

The algorithm processes the input once.

**Example:**

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

```text
Time Complexity: O(n)
```

* * *

**6\. O(n log n) — Linearithmic Time**

Commonly found in efficient sorting algorithms.

**Examples:**

```text
Merge Sort
Heap Sort
Average-case Quick Sort
```

```text
Time Complexity: O(n log n)
```

* * *

**7\. O(n²) — Quadratic Time**

Usually occurs when there are two nested loops.

**Example:**

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

```text
Time Complexity: O(n²)
```

* * *

**8\. O(n³) — Cubic Time**

Usually occurs with three nested loops.

**Example:**

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

```text
Time Complexity: O(n³)
```

* * *

**9\. O(2ⁿ) — Exponential Time**

The number of operations grows exponentially with the input.

**Example:**

```text
Recursive Fibonacci
```

```text
Time Complexity: O(2ⁿ)
```

* * *

**10\. O(n!) — Factorial Time**

The number of operations grows extremely quickly.

**Example:**

```text
Generating all permutations
```

```text
Time Complexity: O(n!)
```

* * *

**Best, Average and Worst Case**

**11\. Best Case**

**Definition:** The minimum amount of work an algorithm performs.

**Example:**

Linear search finds the element at the first position.

```text
Best Case: O(1)
```

* * *

**12\. Average Case**

**Definition:** The expected performance for typical input.

For linear search:

```text
Average Case: O(n)
```

* * *

**13\. Worst Case**

**Definition:** The maximum amount of work an algorithm may perform.

For linear search:

```text
Worst Case: O(n)
```

* * *

**Common Complexity Examples**

| Operation | Time Complexity |
| --- | --- |
| Array access | O(1) |
| Linear Search | O(n) |
| Binary Search | O(log n) |
| HashMap lookup | O(1) average |
| HashSet lookup | O(1) average |
| Merge Sort | O(n log n) |
| Heap Sort | O(n log n) |
| Bubble Sort | O(n²) |
| Selection Sort | O(n²) |
| Insertion Sort | O(n²) |

* * *

**Space Complexity**

**14\. O(1) Space**

Uses a fixed amount of additional memory.

**Example:**

```java
int sum = 0;

for (int i = 0; i < n; i++) {
    sum += i;
}
```

```text
Space Complexity: O(1)
```

* * *

**15\. O(n) Space**

Additional memory grows with input size.

**Example:**

```java
int[] result = new int[n];
```

```text
Space Complexity: O(n)
```

* * *

**16\. O(n²) Space**

Memory grows proportionally to `n²`.

**Example:**

```java
int[][] matrix = new int[n][n];
```

```text
Space Complexity: O(n²)
```

* * *

**Time Complexity vs Space Complexity**

| Time Complexity | Space Complexity |
| --- | --- |
| Measures execution time | Measures memory usage |
| Focuses on operations | Focuses on additional memory |
| Uses Big O notation | Uses Big O notation |
| Example: O(n) | Example: O(n) |

* * *

**How to Find Time Complexity**

### Step 1: Identify the loops

```java
for (...)        // O(n)
```

### Step 2: Check nested loops

```java
for (...) {
    for (...) {
    }
}
```

```text
O(n²)
```

**Step 3: Check sequential operations**

```java
for (...) {}     // O(n)
for (...) {}     // O(n)
```

```text
O(n + n) = O(n)
```

**Step 4: Check recursive calls**

Identify how many times the function calls itself.

```text
Binary Search → O(log n)
```

* * *

**How to Find Space Complexity**

Check the additional data structures created by the algorithm.

```java
int[] arr = new int[n];
```

```text
Space Complexity: O(n)
```

```java
int[][] matrix = new int[n][n];
```

```text
Space Complexity: O(n²)
```

* * *

**Important Rules to Remember**

```text
Single loop             → O(n)

Nested loops            → O(n²)

Three nested loops      → O(n³)

Input divided by 2      → O(log n)

Sorting efficiently     → O(n log n)

Fixed variables         → O(1)

Array of size n         → O(n)

Matrix n × n            → O(n²)
```

* * *

**Conclusion**

Time Complexity helps us measure **how fast an algorithm grows**, while Space Complexity helps us measure **how much additional memory it requires**.

Understanding Big O notation is essential for writing **efficient Java programs and solving DSA problems**.

The most important complexities to remember are:

```text
O(1)       → Constant
O(log n)   → Logarithmic
O(n)       → Linear
O(n log n) → Linearithmic
O(n²)      → Quadratic
O(2ⁿ)      → Exponential
O(n!)      → Factorial
```