# Time complexity

### Code Example: Linear Search

```java
int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // Target found at index i
        }
    }
    return -1; // Target not found
}
```

### Big O Notation (O) - Worst-Case Scenario

* **Scenario**: The target element is at the very end of the array or is not present at all.
    
* **Example**: If the array has 100 elements and the target is the last element or not in the array, the function has to check all 100 elements.
    
* **Big O**: For linear search, the worst-case time complexity is `O(n)`, where `n` is the number of elements in the array. This means in the worst case, the function has to check every single element.
    

### Omega Notation (Ω) - Best-Case Scenario

* **Scenario**: The target element is the very first element in the array.
    
* **Example**: If the target is the first element, the function finds it immediately on the first check.
    
* **Omega**: For linear search, the best-case time complexity is `Ω(1)`, meaning in the best case, you only need one comparison to find the target.
    

### Theta Notation (Θ) - Average or Exact Scenario

* **Scenario**: The target is somewhere in the middle of the array.
    
* **Example**: If the array has 100 elements, on average, the target might be around the 50th element, so the function would need to check about half of the elements.
    
* **Theta**: For linear search, the average-case time complexity is `Θ(n)`, where `n` is the number of elements in the array. This means, on average, you might need to check about half of the array before finding the target.
    

### Summary with Real-Life Analogy

* **Big O (O)**: If you had to search for a book in a library by checking every book, Big O tells you the maximum number of books you'd have to check (i.e., going through all the books).
    
* **Omega (Ω)**: If the first book you pick is the one you need, Omega tells you the minimum number of books you'd check (i.e., just one book).
    
* **Theta (Θ)**: On average, it tells you how many books you might need to check to find the one you’re looking for, considering you might get lucky or unlucky.