DSA Simple Algorithm

What Makes an Algorithm?

An algorithm is a finite, well-defined, step-by-step procedure that takes some input and produces some output. It is not just any set of instructions - to qualify as an algorithm, a procedure must be precise enough that a person or a computer could follow it exactly and always reach an answer.

Computer scientists usually describe algorithms with five defining properties. Keeping these in mind helps you recognize when a piece of pseudocode or a function is actually a well-formed algorithm rather than a vague sketch of an idea.

• Finiteness - it must terminate after a finite number of steps
• Definiteness - each step must be precisely and unambiguously defined
• Input - it takes zero or more well-defined inputs
• Output - it produces one or more well-defined outputs
• Effectiveness - each step must be simple enough to be carried out exactly

Correctness vs. Efficiency

Correctness means an algorithm produces the right answer for every valid input, including edge cases like empty collections or extreme values. Efficiency means how much time and memory it uses while doing so. These are independent qualities: an algorithm can be perfectly correct but too slow to be useful, and a fast algorithm that gives wrong answers on some inputs is worthless no matter how quick it is. Good engineering means proving correctness first, and only then optimizing for efficiency.

def has_duplicate_naive(items):
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                return True
    return False

print(has_duplicate_naive([3, 1, 4, 1, 5]))  # True
print(has_duplicate_naive([3, 1, 4, 9, 5]))  # False

Trace has_duplicate_naive on [3, 1, 4, 1, 5]: comparing index 0 against indices 1 through 4 checks 3 against 1, 4, 1, and 5 with no match, then comparing index 1 against indices 2 through 4 checks 1 against 4 (no match) and 1 against 1 - a match - so the function returns True after 6 total comparisons. The set-based version below reaches the same correct answer after just 4 iterations: it adds 3, 1, and 4 to a seen set, then finds 1 already present and returns True immediately, trading nested comparisons for constant-time set lookups.

def has_duplicate_fast(items):
    seen = set()
    for value in items:
        if value in seen:
            return True
        seen.add(value)
    return False

print(has_duplicate_fast([3, 1, 4, 1, 5]))  # True
print(has_duplicate_fast([3, 1, 4, 9, 5]))  # False

def has_duplicate_fast(items):
    seen = set()
    for value in items:
        if value in seen:
            return True
        seen.add(value)
    return False

print(has_duplicate_fast([]))       # False - empty list
print(has_duplicate_fast([7]))      # False - single element
print(has_duplicate_fast([2, 2]))   # True - smallest duplicate case