Time Complexity & Big-O

    DSA · Beginner

    Definition

    Big-O describes how the running time or memory of an algorithm grows as input size grows.

    Lets you compare solutions and predict whether code will pass limits.

    Diagram

    O(1)O(log n)O(n)O(n log n)O(n²)

    Flowchart

    Count basic operationsExpress in terms of nDrop constantsKeep the dominant term

    Example: Nested loop is O(n²)

    n = 4
count = 0
for i in range(n):
    for j in range(n):
        count += 1
print(count)

    Output: 16

    Key points

    • ~10⁸ simple operations per second is a rough guide
    • Halving the input each step gives log n

    Interview questions

    Is O(2n) different from O(n)?

    No, constants are dropped; both are O(n).

    More DSA topics

    ArraysLinked ListStackQueue