Home/Blog/Programming/Geometric series and classic 'prune and search'

Geometric series and classic 'prune and search'

11 min read

Dec 08, 2023

content

Geometric series: A recap

Bounded geometric series

Proof of the bound of geometric series

Some key observations

Prune and search

Finding the majority element

The pruning strategy

The shrinking procedure will not violate the majority condition

Analysis of this pruning strategy idea

Exercise: What happens if NNN is odd?

C++ implementation

Conclusion and applications

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

Mathematics studies patterns, sequences, and series, aiding in modeling natural phenomena and resolving real-world problems. Among these series, the geometric series stands out for its intriguing characteristics. In this blog, we will explore the concept of geometric series, investigate their cumulative bounds, and become familiar with the algorithmic approach known as prune and search.

Prune and search is a well-known technique for locating centerpoints, originally introduced by Nimrod Megiddo in 1983. Since its inception, it has become a prominent method in the field of algorithms and has found applications across various domains. This algorithmic strategy offers an efficient way to derive solutions from the search domain by progressively reducing the problem size in a geometrically decreasing manner, resulting in a time complexity bounded by the limits of the geometric series.

Geometric series: A recap#

Before we delve into the bounded form, let’s reiterate the concept of a geometric series. A geometric series is an ordered sequence of numbers in which each term is obtained by multiplying the previous term by a fixed, non-zero constant called the common ratio, denoted by $r$ . Mathematically, the series can be represented as:

Algebraic approach

Consider the following: Multiply both sides of the equation by the common ratio $r$ :
$\begin{align} S_n &= a + ar + ar^2 + ar^3 + \ldots + ar^{n-2} + ar^{n-1} \\ rS_n &= ar + ar^2 + ar^3 + ar^4 + \ldots + ar^{n-1} + ar^n \\ S_n - rS_n &= a - ar^n \\ S_n &= \frac{a(1-r^n)}{1-r} \end{align}$

Theorem: In a decreasing positive geometric series where $0<r<1$ the series sum is bounded by the first term.

Proof: Continuing from equation (4), we can easily say that $r^n \to 0$ as $n \to \infty$ .

Therefore, the top equation (4) will become:
$\begin{align} S_n = \frac{a}{1-r} \end{align}$
For all practical purposes, for a fixed value $0<r<1$ , the value of $\frac{1}{1-r}$ will just be constant. Therefore,
$\begin{align} S_n = O(a) \end{align}$
Remember: If a quantity is decreasing (shrinking) by a geometric fixed ratio instance by instance, then the entire summation of that series of all the infinite events will be bounded by a constant time first term.

OR

If a quantity is increasing (expanding) by a geometric fixed ratio ( $r>1$ ), then the series will always be bounded by the last term.

Remark: We leave the second statement as a homework question for you to ponder about.

For example: If we assume $p=\frac{1}{2}$ , the above recurrence seems like a recurrence of the binary search only if $f(N)$ is a constant. But for this blog, we assume that $f(N)$ is at least a linear function, i.e., $O(N^c)$ where $c\geq1$ , that is, we scan through the entire input search space at least once.

The question is, how will we compute the running time of such a recurrence?

Think for a while! Can you see a connection with the above geometric series?

The recurrence sum will look like the following:

If we have $f(N) = N$ and $p = \frac{1}{2}$ , then the summation will look like:

T(N) = N + \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + ... + 8 + 4 + 2 + 1

We know that this summation is bounded by $2N$ i.e., $O(N)$ .

If we have $f(N)=N^2$ , then the summation will look like:

T(N) = N^2 + (\frac{N}{2})^2 + (\frac{N}{4})^2 + (\frac{N}{8})^2 + ... + 1^2

T(N) = N^2 + \frac{N^2}{4} + \frac{N^2}{16} + \frac{N^2}{64} + ... + 1^2

This summation is also bounded by the first term, that is, $O(N^2)$ , due to equation (6), as decreasing geometric series summation is bounded by the first term, and here, the first term is $N^2$ .

Let’s delve into a practical example of the prune-and-search technique in action and evaluate its effectiveness in terms of time complexity.

Finding the majority element#

An element in an array is called a majority element if it appears more than half of the time in an array.

It is obvious to see that there could be at most one majority element in any array.

We would like to solve the following problem:

Given an array/vector of $N$ elements that may or may not contain a majority element, find the majority element (if it exists) in $O(N)$ time.

There are multiple ways to solve this problem:

Naive approach: We find the frequency of every element and report the element with more than half occurrences. This approach will take $O(N^2)$ time.

Using a balanced binary search tree: Using AVL (or any binary search tree), we insert every value in the tree. If the value already exists, we increment its count. We report the element that occurs half of the time. This approach will take $O(N \log N)$ time (as the height of such a tree will be at most $O(log⁡N)$ , and every element must be inserted and searched while maintaining the frequency).

Using hashing: Another approach to solving this problem is by utilizing hashing, which can be done in $O(N)$ time. Assign each element’s value as a key and accumulate the count of each occurrence while calculating the frequency of each element. Afterward, iterate through the hash table and identify the element with the highest frequency as the candidate for the majority element.

Let’s discuss our solution using the classical prune and search approach.

The pruning strategy#

The idea is the following:

We pair up elements arbitrarily.
We compare each pair of elements such that:
1. If the two elements are different, we discard both of them.
2. If the two elements are the same, we choose one of them as a representative.
We repeat the above procedure (steps 1–2) until we are only left with one number. That number is our candidate for the majority element.

Before we look at its time complexity, we should look at its correctness.

The shrinking procedure will not violate the majority condition#

If we assume that the majority element exists, the first step is just pairing up elements, so no pruning is involved in this step.

In the second step of pruning, the majority condition will not be violated. Let’s see why, by looking at it case by case separately:

If the two compared elements are different (one of them could be the majority element), we reject both elements. Therefore, when we reject one majority element, it also removes one of the other elements. Thus, this decision does not break the majority condition.
The only case left is when the two elements are identical (both pairs could be majority or non-majority elements). In that scenario, we select one of the elements. In this pruning scenario, the majority element always retains its majority status. This is because, if the majority element exists, the majority of the pairs will consist of the same elements, with the majority of element pairs being the predominant ones.

Analysis of this pruning strategy idea#

Assume we have $N$ numbers at the beginning of the step; if we look closely at the two pruning steps, the problem size is shrunk to at max $\frac{N}{2}$ , and when we repeat this recursive procedure, the problem size becomes $\frac{N}{4}$ . Therefore the total comparisons will follow this recurrence:

#include <iostream>
#include <vector>
using namespace std;
int findMajorityElement(vector<int>& nums) 
{
    if (nums.size() == 1) 
    {
        return nums[0]; // Base case: Only one element left
    }
    
    int si = 0;
    if(nums.size()%2==1) // odd case
    {
        // let us test the first element as the candidate of majority.
        int count=0;
        for(int i=1; i<nums.size(); i++)
        {
            if(nums[i]==nums[si])
                count++;
        }
        // if nums[0]: is the majority element return 
        // otherwise we can safely reject 0'th element which we are unable to pair 
        if(count>nums.size()/2) // we have found the majority element
            return nums[0];
        
        si++;
    }
    
    vector<int> newVector;
    // for odd case we start from si=1 otherwise si=0
    for (int i = si; i < nums.size(); i += 2) 
    {       
        if (i + 1 < nums.size() && nums[i] == nums[i + 1]) 
        {
            newVector.push_back(nums[i]);
        }
    }
    return findMajorityElement(newVector); // Recursive call
}
int main() {
    vector<int> nums = {4, 3, 4, 2, 4, 4, 2, 4, 4,5}; // Example input
    int majorityElement = findMajorityElement(nums);
    cout << "The majority element is: " << majorityElement << endl;
    
    return 0;
}

Lines 7–10: This is the base condition. That is, if we have only one number left, the potential majority element.
Line 13: We separate the odd case and make sure that if we have such a case, the first element is to be checked as the majority element by instantly checking and declaring whether it is the majority element or rejecting this unpaired element.
Lines 16–21: We count the occurrence of the fixed first element (as the potential candidate).
Lines 24–25: We check if this is the majority element; we return that value, and no need to check any other further.
Line 27: If this line executes, we can safely ignore the first element; therefore, we increment si by 1 so that the next comparison starts from the index 1 instead of 0 (making sure we have even candidates), and the pruning process can be applied.
Lines 32–38: Here, we compare the pair and select the left element as a representative (by adding it into newVector) in case both elements are matched, or reject both if they are unmatched (making sure that if one element of the majority element gets rejected along with that, a non-majority element gets rejected too, therefore the majority remains in the majority).

Conclusion and applications#

The prune and search technique stands as an elegant application of geometric series principles. It operates on the fundamental premise that in cases where we encounter a geometrically decreasing function, such as the cost associated with each step where the search space consistently contracts by a common ratio, the overall cost remains bounded by the value of the initial term. This approach leverages the inherent property of the bound of geometric series, enabling elegant and efficient solutions.

The applications of this technique are multifaceted and extend to various domains. For instance, in deterministic quicksort, the process of finding the $K$ -th smallest element relies on a similar pruning technique, demonstrating the versatility of this approach in sorting and searching algorithms. Additionally, in the realm of deep learning, when training deep neural networks, layers often geometrically shrink through techniques like max/min/average pooling.

Grokking Coding Interview Patterns in C++

Grokking the Coding Interview Patterns

With thousands of potential questions to account for, preparing for the coding interview can feel like an impossible challenge. Yet with a strategic approach, coding interview prep doesn’t have to take more than a few weeks. Stop drilling endless sets of practice problems, and prepare more efficiently by learning coding interview patterns. This course teaches you the underlying patterns behind common coding interview questions. By learning these essential patterns, you will be able to unpack and answer any problem the right way — just by assessing the problem statement. This approach was created by FAANG hiring managers to help you prepare for the typical rounds of interviews at major tech companies like Apple, Google, Meta, Microsoft, and Amazon. Before long, you will have the skills you need to unlock even the most challenging questions, grok the coding interview, and level up your career with confidence. This course is also available in JavaScript, Python, Go, and C++ — with more coming soon!

85hrs

Intermediate

345 Challenges

346 Quizzes

Beginner to Advanced Computing and Logic Building

This course focuses on building logic to solve simple to advanced coding problems. You will learn advanced computational techniques to solve real-world problems. The solutions for most problems are curated in a way that each solution is followed by a more efficient one, enabling you to devise the most efficient algorithm from the start. The course starts with the fundamentals of variables, loops, and arrays, and progresses to more advanced concepts such as creating games like Gomoku, Word Search, and Game of Life using the divide and conquer approach. The course also includes a built-in debugger to help you understand the code by setting breakpoints and analyzing variable values. Concepts will be demonstrated via animations and illustrations to engage your interest and give you hands-on experience in building interactive games. By the end of the course, you will be well-prepared to tackle coding challenges commonly found in FAANG interviews.

46hrs

Beginner

31 Challenges

44 Quizzes

Written By:

Sarfraz Raza

Join 2.5 million developers at

Explore the catalog

Free Resources

Geometric series and classic 'prune and search'

Geometric series: A recap#

Bounded geometric series#

Proof of the bound of geometric series#

Some key observations#

Prune and search#

Finding the majority element#

The pruning strategy#

The shrinking procedure will not violate the majority condition#

Analysis of this pruning strategy idea#

Exercise: What happens if NNN is odd?#

C++ implementation#

Conclusion and applications#