Exponentiation
Computing the exponentiation of a number is a classic problem in computer science. The problem is to find the value of a number raised to the power of anothe...
Exponentiation
Computing the exponentiation of a number is a classic problem in computer science. The problem is to find the value of a number raised to the power of another number. The algorithm has a number of different implementations with different time complexities. The following are some of the most common implementations of the algorithm and an analysis of their time complexity.
Table of Contents
Linear implementation
There is many ways to implement the exponentiation algorithm. The most common way is to use a loop to multiply the base number by itself the number of times specified by the exponent. This implementation has a time complexity of \(O(n)\) where \(n\) is the exponent.
public static long power(int x, int n) {
long result = 1;
for (int i = 0; i < n; i++) {
result *= x;
}
return result;
}
Another way to implement the exponentiation algorithm is to use recursion according to the following formula: \(x^n = x \times x^{n-1}\). This implementation has a time complexity of \(O(n)\) where \(n\) is the exponent.
public static long power(int x, int n) {
if (n == 0) {
return 1;
} else {
return x * power(x, n - 1);
}
}
We can also follow the following formula: \(x^n = x^{n/2} \times x^{n/2}\) if \(n\) is even and \(x^n = x \times x^{n/2} \times x^{n/2}\) if \(n\) is odd. This implementation has a time complexity of \(O(n)\) where \(n\) is the exponent because it has to calculate the power of \(x\) for each half of the exponent.
public static long power(int x, int n) {
if (n == 0) {
return 1;
} else {
if (n % 2 == 0) {
return power(x, n / 2) * power(x, n / 2);
} else {
return x * power(x, n / 2) * power(x, n / 2);
}
}
}
Logarithmic implementation
The recursive implementation can be optimized by using the following formula: \(x^n = (x^{n/2})^2\) if \(n\) is even and \(x^n = x \times (x^{n/2})^2\) if \(n\) is odd. This implementation has a time complexity of \(O(logn)\) where \(n\) is the exponent.
public static long power(int x, int n) {
if (n == 0) {
return 1;
} else {
long temp = power(x, n / 2);
if (n % 2 == 0) {
return temp * temp;
} else {
return x * temp * temp;
}
}
}
Or we can write the above implementation in a more concise way as follows:
public static long power(int x, int n) {
if (n == 0) {
return 1;
} else {
return n % 2 == 0 ? power(x*x, n / 2): x * power(x*x, n / 2);
}
}
2025
The maximum subsequence sum algorithm
The maximum subsequence sum algorithm is a classic problem in computer science. The problem is to find the maximum sum of a contiguous subsequence in an arra...
2024
Docker
In this post, I will explain a very indispensable tool for developers. Docker is a tool that allows developers to build, deploy, and run applications using c...
Generating permutations
In this post, we will discuss the problem of generating all permutations of a given set of elements. A permutation is an arrangement of elements in a specifi...
The Convex Hull Problem
The convex hull problem is a problem in computational geometry. It is about finding the smallest convex polygon that contains a given set of points. The conv...
2023
CS3401 Projects 1445 1st semester
Project 1: Project management system The aim of this project is to implement a program (java or python) that manages a list of tasks in a project. The pr...
2022
List of projects for CS3401
Use the form link to choose a project :