Big O Practice: Early Return Sorted

def contains_target(sorted_arr, target):
    for x in sorted_arr:
        if x == target:
            return True
        if x > target:
            return False
    return False

Variables

• n - length of the sorted input array

Explanation

The early return makes some inputs return in O(1) - but big-O describes the **worst case**: target absent and larger than every element. Worst case is **O(n)**. The best case is O(1), the average depends on distribution. Big-O conventions ignore best/average unless stated.

More Big O practice problems · Today's daily problem