Check if Number is Even or Odd Using Bits in DSA C - Time & Space Complexity

Time Complexity: Check if Number is Even or Odd Using Bits

O(1)

Understanding Time Complexity

We want to understand how fast the bit check method works to find if a number is even or odd.

How does the time needed change as the number gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>

int isEven(int num) {
    return (num & 1) == 0;
}

int main() {
    int number = 10;
    if (isEven(number)) {
        printf("Even\n");
    } else {
        printf("Odd\n");
    }
    return 0;
}
    

This code uses a bitwise AND to check the last bit of the number to decide if it is even or odd.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single bitwise AND operation.
• How many times: Exactly once per function call.

How Execution Grows With Input

The operation does not depend on the size of the input number; it always checks just one bit.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The number of operations stays the same no matter how big the number is.

Final Time Complexity

Time Complexity: O(1)

This means the check takes the same small amount of time no matter how large the number is.

Common Mistake

[X] Wrong: "Checking if a number is even using bits takes longer for bigger numbers because the number has more bits."

[OK] Correct: The operation only looks at the last bit, so it does not matter how many bits the number has.

Interview Connect

Knowing this quick bit check shows you understand how computers use bits, which is a handy skill for many coding problems.

Self-Check

"What if we checked the second last bit instead of the last bit? How would the time complexity change?"