Time Complexity: Left shift and right shift
O(1)
0
0
Left shift and right shift in C - Time & Space Complexity
Understanding Time Complexity
We want to see how fast the program runs when using left and right shift operations.
How does the number of steps change when we shift bits in a number?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
int leftShift(int x, int n) {
return x << n;
}
int rightShift(int x, int n) {
return x >> n;
}
This code shifts the bits of an integer left or right by n positions.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Bit shifting done by the CPU in one step.
- How many times: The shift happens once per function call, no loops involved.
How Execution Grows With Input
Shifting bits is done in a single CPU instruction regardless of how many bits we shift.
| Input Size (n) | Approx. Operations |
|---|---|
| 1 | 1 operation |
| 10 | 1 operation |
| 100 | 1 operation |
Pattern observation: The time to shift does not grow with the number of bits shifted.
Final Time Complexity
Time Complexity: O(1)
This means shifting bits takes the same amount of time no matter how many bits you shift.
Common Mistake
[X] Wrong: "Shifting by more bits means the program takes longer to run because it moves each bit one by one."
[OK] Correct: The CPU does the shift in one step, not bit by bit, so the time stays the same.
Interview Connect
Understanding that bit shifts are constant time helps you explain how low-level operations work efficiently in real programs.
Self-Check
"What if we replaced the shift operations with a loop that shifts one bit at a time? How would the time complexity change?"