Algorithms - lesson 1 | HackIndia Skills

Why Big-O matters

In placement rounds, the interviewer is not only checking if your code works. They are checking if it still works when the input becomes large.

Big-O is the short way to say how your time or memory grows as input size grows. It helps you choose a better approach before you waste time coding.

Key point

One idea

Big-O ignores exact seconds and focuses on growth. Ask: if n doubles, does my work stay almost same, double, or become much worse?

For interviews and your repo, mention both time complexity and space complexity for each solution.

Common growth rates

Use these as a placement cheat sheet. O(1) is constant work. O(log n) cuts the search area. O(n) scans once. O(n log n) is common in efficient sorting. O(n²) checks pairs. O(2ⁿ) often appears in brute force subsets.

You do not need a proof in most interviews. You need a clear reason linked to loops, recursion, data structures, or sorting.

Example

Loop reading

Read code like a cost meter. Count how many times the main operation runs as n grows.

This example compares one scan with a pair check.

def has_zero(nums):
    for x in nums:
        if x == 0:
            return True
    return False
# Time: O(n), because in the worst case we scan every number.
# Space: O(1), because we use no extra data structure.


def has_pair_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False
# Time: O(n^2), because we check many pairs.
# Space: O(1).

Your to-do

How to estimate

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Name n as the input size, such as number of array items or graph nodes.
Find the loop, recursion, sort, or data structure operation that dominates runtime.
Drop constants, such as O(2n) becoming O(n).
Keep the fastest-growing term, such as O(n² + n) becoming O(n²).
State extra memory separately from input memory.

0 of 5 done

Common mistake

Do not average casually

Beginners often say a search is O(1) because the answer may be found early. In interviews, start with worst-case unless asked otherwise.

If the target is last or missing, a simple scan still checks every item. That is O(n).

Tip

Use AI carefully

You can ask ChatGPT, Gemini, or Claude to review your complexity note. Paste only your function and ask: “Give time and space complexity. Explain using loops or data structures.”

Check the answer yourself. AI often misses hidden costs like sorting, slicing, copying arrays, recursion stack space, or nested loops inside helper functions.