Bitwise NOT in C - Time & Space Complexity

Time Complexity: Bitwise NOT

O(n)

Understanding Time Complexity

Let's see how fast the bitwise NOT operation runs in a program.

We want to know how the time it takes changes when we use it on different input sizes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int bitwise_not(unsigned int x) {
    return ~x;
}

unsigned int array_not(unsigned int arr[], int n) {
    unsigned int result = 0;
    for (int i = 0; i < n; i++) {
        result += ~arr[i];
    }
    return result;
}
    

This code flips all bits of each number in an array and sums the results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise NOT (~) applied to each array element.
• How many times: Once per element, so n times for an array of size n.

How Execution Grows With Input

Each element in the array gets its bits flipped once, so the work grows as the array grows.

Input Size (n)	Approx. Operations
10	10 bitwise NOT operations
100	100 bitwise NOT operations
1000	1000 bitwise NOT operations

Pattern observation: The number of operations grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the task grows in a straight line as the input size grows.

Common Mistake

[X] Wrong: "Bitwise NOT is slow because it changes every bit individually."

[OK] Correct: Bitwise NOT is a single fast operation done by the processor, so it takes constant time per element.

Interview Connect

Understanding how simple bitwise operations scale helps you explain efficiency clearly in interviews.

Self-Check

"What if we applied bitwise NOT inside a nested loop over the array? How would the time complexity change?"