# Lower Bound Theory

In this article, we will learn about the **concept of Lower Bound Theory** and the proofing techniques that are useful for obtaining lower bounds.

Submitted by Shivangi Jain, on July 25, 2018

## Lower Bound Theory

Lower bound **(L(n))** is a property of the specific problem i.e. the sorting problem, matrix multiplication not of any particular algorithm solving that problem.

**Lower bound theory** says that no algorithm can do the job in fewer than that of **(L (n))** times the units for arbitrary inputs i.e. that for every comparison based sorting algorithm must take at least **L(n)** time in the worst case.

**L(n)** is the minimum over all possible algorithm which is maximum complete.

**Trivial lower bounds** are used to yield the bound best option is to count the number of item in the problems input that must be processed and a number of output items that need to be produced.

**The lower bound theory** is the technique that has been used to establish the given algorithm in the most efficient way which is possible. This is done by discovering a function **g(n)** that is a lower bound on the time that any algorithm must take to solve the given problem. Now if we have an algorithm whose computing time is the same order as **g(n)**, then we know that asymptotically we cannot do better.

If **f(n)** is the time for some algorithm, then we write **f(n) = Ω(g(n))** to mean that **g(n)** is the **lower bound of f(n)**. This equation can be formally written, if there exists positive constants **c** and **n0** such that **|f(n)| >= c|g(n)|** for all **n > n0**. In addition for developing lower bounds within the constant factor, we are more conscious of the fact to determine more exact bounds whenever this is possible.

Deriving good **lower bounds** is more difficult than devising efficient algorithms. This happens because a lower bound states a fact about all possible algorithms for solving a problem. Generally, we cannot enumerate and analyze all these algorithms, so lower bound proofs are often hard to obtain.

**The proofing techniques that are useful for obtaining lower bounds are:**

**Comparison trees:**

Comparison trees are the computational model useful for determining lower bounds for sorting and searching problems.**Oracles and adversary arguments:**

One of the techniques that are important for obtaining lower bounds consists of making the use of an oracle**Lower bounds through reduction:**

This is a very important technique of lower bound, This technique calls for reducing the given problem for which a lower bound is already known.**Techniques for the algebraic problem:**

Substitution and linear independence are two methods used for deriving lower bounds on algebraic and arithmetic problems. The algebraic problems are operation on integers, polynomials, and rational functions.

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- P and NP problems and solutions | Algorithms
- 2 – 3 Trees Algorithm
- Midpoint Circle Algorithm
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

Comments and Discussions!