Time complexity

Code Example: Linear Search

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.