WikiGalaxy
Exponential Complexity
Understanding Exponential Complexity
Exponential complexity refers to an algorithm whose growth doubles with each addition to the input data set. This can be represented as O(2^n), where n is the size of the input. Such algorithms can become inefficient and impractical even for relatively small input sizes.
Example 1: Fibonacci Sequence
Fibonacci Calculation
A classic example of exponential complexity is the naive recursive calculation of Fibonacci numbers, where each function call spawns two more calls.
public class Fibonacci {
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
System.out.println(fib(5)); // Output: 5
}
}
Console Output:
5
Example 2: Subset Sum Problem
Subset Sum Problem
The subset sum problem involves determining if a subset of numbers from a set adds up to a specific target sum. The recursive solution explores all possible subsets, leading to exponential complexity.
public class SubsetSum {
static boolean isSubsetSum(int[] set, int n, int sum) {
if (sum == 0) return true;
if (n == 0) return false;
if (set[n - 1] > sum) return isSubsetSum(set, n - 1, sum);
return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);
}
public static void main(String[] args) {
int[] set = {3, 34, 4, 12, 5, 2};
int sum = 9;
System.out.println(isSubsetSum(set, set.length, sum)); // Output: true
}
}
Console Output:
true
Example 3: Traveling Salesman Problem
Traveling Salesman Problem
The Traveling Salesman Problem (TSP) involves finding the shortest possible route that visits a set of cities and returns to the origin city. The brute-force approach checks all permutations of cities, resulting in exponential complexity.
import java.util.*;
public class TSP {
static int tsp(int[][] graph, boolean[] v, int currPos, int n, int count, int cost, int ans) {
if (count == n && graph[currPos][0] > 0) {
ans = Math.min(ans, cost + graph[currPos][0]);
return ans;
}
for (int i = 0; i < n; i++) {
if (!v[i] && graph[currPos][i] > 0) {
v[i] = true;
ans = tsp(graph, v, i, n, count + 1, cost + graph[currPos][i], ans);
v[i] = false;
}
}
return ans;
}
public static void main(String[] args) {
int[][] graph = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
boolean[] v = new boolean[graph.length];
v[0] = true;
int ans = Integer.MAX_VALUE;
ans = tsp(graph, v, 0, graph.length, 1, 0, ans);
System.out.println(ans); // Output: 80
}
}
Console Output:
80
Example 4: Power Set Generation
Power Set Generation
Generating the power set of a set involves creating all possible subsets. The size of the power set is 2^n, where n is the number of elements in the original set, indicating exponential complexity.
import java.util.*;
public class PowerSet {
static void printPowerSet(int[] set) {
int n = set.length;
for (int i = 0; i < (1 << n); i++) {
System.out.print("{ ");
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) > 0) {
System.out.print(set[j] + " ");
}
}
System.out.println("}");
}
}
public static void main(String[] args) {
int[] set = {1, 2, 3};
printPowerSet(set);
}
}
Console Output:
{ } { 1 } { 2 } { 1 2 } { 3 } { 1 3 } { 2 3 } { 1 2 3 }
Example 5: Permutations of a String
Permutations of a String
Finding all permutations of a string involves generating all possible arrangements of its characters. The number of permutations is n!, leading to exponential complexity as n grows.
public class Permutations {
static void permute(String str, String answer) {
if (str.length() == 0) {
System.out.println(answer);
return;
}
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
String ros = str.substring(0, i) + str.substring(i + 1);
permute(ros, answer + ch);
}
}
public static void main(String[] args) {
String s = "ABC";
permute(s, "");
}
}
Console Output:
ABC ACB BAC BCA CAB CBA
