Home › DSA › Foundations

Logarithmic Time and Space Olog n

Logarithmic Time Complexity and Logarithmic Space Complexity occur in algorithms that repeatedly reduce the problem size by a constant factor (often halving). This type of complexity is common in algorithms that use recursive division, such as finding powers or performing binary searches.

Key Characteristics

In an algorithm with time and space complexity:

Time Complexity: The runtime grows logarithmically as the input size increases, due to dividing the problem in each step.
Space Complexity: The memory usage grows logarithmically with the input size due to the depth of the recursive call stack.

Code Example

Here’s a recursive example that demonstrates complexity. This function calculates the largest power of two less than or equal to a given number, n, by repeatedly halving n.

java

class Solution {

  public int largest_power_of_two(int n) {
    if (n <= 1) {
      return 0;
    } else {
      return 1 + largest_power_of_two(n / 2);
    }
  }

  public static void main(String[] args) {
    int number = 20; // Example number

    Solution solution = new Solution();
    int result = solution.largest_power_of_two(number);

    System.out.println(
      "Largest power of 2 exponent for " + number + " is: " + result
    );
  }
}

Explanation: This function keeps dividing n by 2 until n becomes 1 or less, adding 1 to the count at each step.

Analyzing the Time Complexity Using Recurrence Relation

To understand the time complexity, let’s set up a recurrence relation for the function:

Step 1: Define the Recurrence Relation

Let represent the time complexity of largest_power_of_two for an input of size n.
Each time we call largest_power_of_two(n // 2), we halve n, so we can express the time complexity as:

Here:

represents the recursive call with input size halved.
represents the constant work done in each recursive step (the addition).

Step 2: Solve the Recurrence Relation

Let’s expand this recurrence relation step by step to understand the total number of recursive calls.

The process continues until the input size is reduced to 1, at which point the function stops. This happens when , which simplifies to:

Taking the logarithm of both sides, we get:

So, because there are recursive calls before reaching the base case.

Analyzing Space Complexity Using Recurrence Relation

The space complexity also grows logarithmically because each recursive call uses a stack frame, and the maximum number of stack frames corresponds to the depth of recursion.

Define the Space Recurrence Relation:
- Let represent the space complexity.
- Each recursive call adds one frame to the call stack, and the stack grows as the input is halved:

Recursive Depth and Space Complexity:
- Similar to the time complexity, the recursion depth reaches .
- Therefore, the space complexity is also:

🤖 Don't fully get this? Learn it with Claude

Stuck on Logarithmic Time and Space Olog n? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Logarithmic Time and Space Olog n** (DSA) and want to truly understand it. Explain Logarithmic Time and Space Olog n from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Logarithmic Time and Space Olog n** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Logarithmic Time and Space Olog n** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Logarithmic Time and Space Olog n** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Space Complexity Analysis of Recur Linearithmic Time On log n →