Examples To Demonstrate Logarithmic Time Complexity
Example 1: loga b
Task: We have a number N which has an initial value of 16 and the task is to reduce the given number to 1 by repeated division of 2.
Approach:
- Initialize a variable number_of_operation with a value 0 .
- Run a for loop from N till 1.
- In each iteration reduce the value of N to half.
- Increment the number_of_operation variable by one.
- Return the number_of_operation variable.
Implementation:
// C++ code for reducing a number to its logarithm
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N = 16;
int number_of_operations = 0;
cout << "Logarithmic reduction of N: ";
for (int i = N; i > 1; i = i / 2) {
cout << i << " ";
number_of_operations++;
}
cout << '\n'
<< "Algorithm Runtime for reducing N to 1: "
<< number_of_operations;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main (String[] args) {
int N = 16;
int number_of_operations = 0;
System.out.print("Logarithmic reduction of N: ");
for (int i = N; i > 1; i = i / 2) {
System.out.print(i + " ");
number_of_operations++;
}
System.out.println();
System.out.print("Algorithm Runtime for reducing N to 1: " + number_of_operations);
}
}
# python3 code for the above approach
# Driver Code
if __name__ == "__main__":
N = 16
number_of_operations = 0
print("Logarithmic reduction of N: ", end = "")
i = N
while(i>1) :
print( i , end = " ")
number_of_operations += 1
i = i // 2
print()
print("Algorithm Runtime for reducing N to 1:", number_of_operations)
# This code is contributed by sanjoy_62.
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG {
// Driver Code
public static void Main()
{
int N = 16;
int number_of_operations = 0;
Console.Write("Logarithmic reduction of N: ");
for (int i = N; i > 1; i = i / 2) {
Console.Write(i + " ");
number_of_operations++;
}
Console.WriteLine();
Console.WriteLine("Algorithm Runtime for reducing N to 1: " + number_of_operations);
}
}
let number_of_operations = 0;
let n= 16;
for(let i=n; i>1; i=i/2) {
console.log(i);
number_of_operations++;
}
console.log(number_of_operations);
Output
Logarithmic reduction of N: 16 8 4 2 Algorithm Runtime for reducing N to 1: 4
Explanation:
It is clear from the above algorithm that in each iteration the value is divided by a factor of 2 starting from 16 till it reaches 1, it takes 4 operations.
As the input value gets reduced by a factor of 2, In mathematical terms the number of operations required in this case is log2(N), i.e. log2(16) = 4.So, in terms of time complexity, the above algorithm takes logarithmic runtime to complete i.e. log2(N).
Example 2: Binary search algorithm (log N)
Linearly Searching a value in an array of size N can be very hectic, even when the array is sorted but using binary search this can be done in a lot easier way and in lesser time as the algorithm reduces the search space by half in each operation thus gives a complexity of log2(N), Here base is 2 because process repeatedly reduces to half.
Consider an array Arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18}, If it is required to find the index of 8 then the algorithm will work as following:
// C++ program for finding the index of 8
#include <iostream>
using namespace std;
int find_position(int val, int Arr[], int n, int& steps)
{
int l = 0, r = n - 1;
while (l <= r) {
steps++;
int m = l + (r - l) / 2;
if (Arr[m] == val)
return m;
else if (Arr[m] < val)
l = m + 1;
else
r = m - 1;
}
return -1;
}
// Driver Code
int main()
{
int Arr[8] = { 2, 4, 6, 8, 10, 12, 14, 16 };
int steps = 0;
// Function Call
int idx = find_position(8, Arr, 8, steps);
cout << "8 was present on index: "<<idx << endl;
// Since the worst case runtime of Binary search is
// log(N) so the count of steps must be less than log(N)
cout << "Algorithm Runtime: " << steps << endl;
return 0;
}
// Java program for finding the index of 8
import java.io.*;
class GFG {
static int steps = 0;
static int find_position(int val, int Arr[], int n)
{
int l = 0, r = n - 1;
while (l <= r) {
steps++;
int m = l + (r - l) / 2;
if (Arr[m] == val)
return m;
else if (Arr[m] < val)
l = m + 1;
else
r = m - 1;
}
return -1;
}
// Driver Code
public static void main (String[] args)
{
int Arr[] = { 2, 4, 6, 8, 10, 12, 14, 16 };
steps = 0;
// Function Call
int idx = find_position(8, Arr, 8);
System.out.println("8 was present on index: "+idx);
// Since the worst case runtime of Binary search is
// log(N) so the count of steps must be less than log(N)
System.out.println("Algorithm Runtime: " + steps);
}
}
// This code is contributed by Aman Kumar
# Python program for finding the index of 8
def find_position(val,Arr,n):
global steps
l=0
r=n-1
while(l<=r):
steps+=1
m=l+(r-l)//2
if(Arr[m] == val):
return m
elif(Arr[m] < val):
l=m+1
else:
l=m-1
return -1
# Driver code
Arr=[2, 4, 6, 8, 10, 12, 14, 16]
steps=0
# Function Call
idx = find_position(8, Arr, 8)
print("8 was present on index: {0}".format(idx))
# Since the worst case runtime of Binary search is
# log(N) so the count of steps must be less than log(N)
print("Algorithm Runtime: {0}".format(steps))
# This code is contributed by Pushpesh Raj.
using System;
namespace GFG {
class Program {
static int steps = 0;
static int FindPosition(int val, int[] arr, int n) {
int l = 0, r = n - 1;
while (l <= r) {
steps++;
int m = l + (r - l) / 2;
if (arr[m] == val) {
return m;
}
else if (arr[m] < val) {
l = m + 1;
}
else {
r = m - 1;
}
}
return -1;
}
static void Main(string[] args) {
int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16 };
steps = 0;
int idx = FindPosition(8, arr, 8);
Console.WriteLine("8 was present on index: " + idx);
Console.WriteLine("Algorithm runtime: " + steps);
}
}
}
//This code is contributed by Edula Vinay Kumar Reddy
// JavaScript program for finding the index of 8
let steps = 0;
function find_position(val, Arr, n) {
let l = 0;
let r = n - 1;
while (l <= r) {
steps += 1;
let m = Math.floor(l + (r - l) / 2);
if (Arr[m] === val) {
return m;
} else if (Arr[m] < val) {
l = m + 1;
} else {
r = m - 1;
}
}
return -1;
}
// Driver code
let Arr = [2, 4, 6, 8, 10, 12, 14, 16];
// Function Call
let idx = find_position(8, Arr, 8);
console.log(`8 was present on index: ${idx}`);
// Since the worst case runtime of Binary search is
// log(N) so the count of steps must be less than log(N)
console.log(`Algorithm Runtime: ${steps}`);
Output
8 was present on index: 3 Algorithm Runtime: 1
Explanation:
Binary search works on Divide and conquer approach, In above example In worst case 3 comparisons will be needed to find any value in array. Also the value of log (N) where N is input size i.e. 8 for above example will be 3. Hence the algorithm can be said to exhibit logarithmic time complexity.
Example 3: Binary search algorithm (log log N)
An example where the time complexity of algorithm is Double logarithmic along with a length factor N is when prime numbers from 1 to N need to be found.
#include <bits/stdc++.h>
using namespace std;
const long long MAX_SIZE = 1000001;
// isPrime[] : isPrime[i] is true if number is prime
// prime[] : stores all prime number less than N
// SPF[] that store smallest prime factor of number
// [for Exp : smallest prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
vector<long long> isprime(MAX_SIZE, true);
vector<long long> prime;
vector<long long> SPF(MAX_SIZE);
// Function generate all prime number less than N in O(n)
void manipulated_seive(int N)
{
// 0 and 1 are not prime
isprime[0] = isprime[1] = false;
// Fill rest of the entries
for (long long int i = 2; i < N; i++) {
// If isPrime[i] == True then i is
// prime number
if (isprime[i]) {
// put i into prime[] vector
prime.push_back(i);
// A prime number is its own smallest
// prime factor
SPF[i] = i;
}
// Remove all multiples of i*prime[j] which are
// not prime by making isPrime[i*prime[j]] = false
// and put smallest prime factor of i*Prime[j] as
// prime[j] [ for exp :let i = 5 , j = 0 , prime[j]
// = 2 [ i*prime[j] = 10 ] so smallest prime factor
// of '10' is '2' that is prime[j] ] this loop run
// only one time for number which are not prime
for (long long int j = 0;
j < (int)prime.size() && i * prime[j] < N
&& prime[j] <= SPF[i];
j++) {
isprime[i * prime[j]] = false;
// put smallest prime factor of i*prime[j]
SPF[i * prime[j]] = prime[j];
}
}
}
// Driver program to test above function
int main()
{
int N = 13; // Must be less than MAX_SIZE
manipulated_seive(N);
// Print all prime number less than N
for (int i = 0; i < prime.size() && prime[i] <= N; i++)
cout << prime[i] << " ";
return 0;
}
import java.util.*;
public class Main {
static final int MAX_SIZE = 1000001;
// isprime[] : isprime[i] is true if number is prime
// prime[] : stores all prime numbers less than N
// SPF[] that store smallest prime factor of number
// [for Exp : smallest prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
static boolean[] isprime = new boolean[MAX_SIZE];
static List<Integer> prime = new ArrayList<Integer>();
static int[] SPF = new int[MAX_SIZE];
// Function generate all prime numbers less than N in
// O(n)
static void manipulated_seive(int N)
{
Arrays.fill(isprime, true);
// 0 and 1 are not prime
isprime[0] = isprime[1] = false;
// Fill rest of the entries
for (int i = 2; i < N; i++) {
// If isprime[i] is true then i is prime number
if (isprime[i]) {
// put i into prime[] list
prime.add(i);
// A prime number is its own smallest prime
// factor
SPF[i] = i;
}
// Remove all multiples of i*prime[j] which are
// not prime by making isprime[i*prime[j]] =
// false and put the smallest prime factor of
// i*Prime[j] as prime[j] [for example: let i =
// 5, j = 0, prime[j] = 2 [i*prime[j] = 10] so
// the smallest prime factor of '10' is '2' that
// is prime[j]] this loop runs only one time for
// numbers which are not prime
for (int j = 0;
j < prime.size() && i * prime.get(j) < N
&& prime.get(j) <= SPF[i];
j++) {
isprime[i * prime.get(j)] = false;
// put the smallest prime factor of
// i*prime[j]
SPF[i * prime.get(j)] = prime.get(j);
}
}
}
// Driver program to test above function
public static void main(String[] args)
{
int N = 13; // Must be less than MAX_SIZE
manipulated_seive(N);
// Print all prime numbers less than N
for (int i = 0;
i < prime.size() && prime.get(i) <= N; i++) {
System.out.print(prime.get(i) + " ");
}
}
}
// This code is contributed by divyansh2212
import math
MAX_SIZE = 1000001
# isprime[]: isprime[i] is True if number is prime
# prime[]: stores all prime numbers less than N
# SPF[] that store smallest prime factor of number
# [for Exp: smallest prime factor of '8' and '16'
# is '2' so we put SPF[8] = 2, SPF[16] = 2]
isprime = [True] * MAX_SIZE
prime = []
SPF = [0] * MAX_SIZE
# Function generate all prime numbers less than N in O(n)
def manipulated_seive(N):
global isprime, prime, SPF
# 0 and 1 are not prime
isprime[0] = isprime[1] = False
# Fill rest of the entries
for i in range(2, N):
# If isprime[i] is True then i is prime number
if isprime[i]:
# put i into prime[] list
prime.append(i)
# A prime number is its own smallest prime factor
SPF[i] = i
# Remove all multiples of i*prime[j] which are
# not prime by making isprime[i*prime[j]] = False
# and put the smallest prime factor of i*Prime[j] as
# prime[j] [for example: let i = 5, j = 0, prime[j]
# = 2 [i*prime[j] = 10] so the smallest prime factor
# of '10' is '2' that is prime[j]] this loop runs
# only one time for numbers which are not prime
j = 0
while j < len(prime) and i * prime[j] < N and prime[j] <= SPF[i]:
isprime[i * prime[j]] = False
# put the smallest prime factor of i*prime[j]
SPF[i * prime[j]] = prime[j]
j += 1
# Driver program to test above function
if __name__ == "__main__":
N = 13 # Must be less than MAX_SIZE
manipulated_seive(N)
# Print all prime numbers less than N
for i in range(len(prime)):
if prime[i] <= N:
print(prime[i], end=" ")
else:
break
using System;
using System.Collections.Generic;
class MainClass
{
static readonly int MAX_SIZE = 1000001;
// isprime[] : isprime[i] is true if number is prime
// prime[] : stores all prime numbers less than N
// SPF[] that store smallest prime factor of number
// [for Exp : smallest prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
static bool[] isprime = new bool[MAX_SIZE];
static List<int> prime = new List<int>();
static int[] SPF = new int[MAX_SIZE];
// Function generate all prime numbers less than N in
// O(n)
static void manipulated_seive(int N)
{
Array.Fill(isprime, true);
// 0 and 1 are not prime
isprime[0] = isprime[1] = false;
// Fill rest of the entries
for (int i = 2; i < N; i++)
{
// If isprime[i] is true then i is prime number
if (isprime[i])
{
// put i into prime[] list
prime.Add(i);
// A prime number is its own smallest prime
// factor
SPF[i] = i;
}
// Remove all multiples of i*prime[j] which are
// not prime by making isprime[i*prime[j]] =
// false and put the smallest prime factor of
// i*Prime[j] as prime[j] [for example: let i =
// 5, j = 0, prime[j] = 2 [i*prime[j] = 10] so
// the smallest prime factor of '10' is '2' that
// is prime[j]] this loop runs only one time for
// numbers which are not prime
for (int j = 0;
j < prime.Count && i * prime[j] < N
&& prime[j] <= SPF[i];
j++)
{
isprime[i * prime[j]] = false;
// put the smallest prime factor of
// i*prime[j]
SPF[i * prime[j]] = prime[j];
}
}
}
// Driver program to test above function
public static void Main(string[] args)
{
int N = 13; // Must be less than MAX_SIZE
manipulated_seive(N);
// Print all prime numbers less than N
for (int i = 0;
i < prime.Count && prime[i] <= N; i++)
{
Console.Write(prime[i] + " ");
}
}
}
const MAX_SIZE = 1000001;
// isprime[]: isprime[i] is true if number is prime
// prime[]: stores all prime numbers less than N
// SPF[] that store smallest prime factor of number
// [for Exp: smallest prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2, SPF[16] = 2]
let isprime = Array(MAX_SIZE).fill(true);
let prime = [];
let SPF = Array(MAX_SIZE).fill(0);
// Function generate all prime numbers less than N in O(n)
function manipulated_seive(N) {
// 0 and 1 are not prime
isprime[0] = isprime[1] = false;
// Fill rest of the entries
for (let i = 2; i < N; i++) {
// If isprime[i] is true then i is prime number
if (isprime[i]) {
// put i into prime[] list
prime.push(i);
// A prime number is its own smallest prime factor
SPF[i] = i;
}
// Remove all multiples of i*prime[j] which are
// not prime by making isprime[i*prime[j]] = false
// and put the smallest prime factor of i*Prime[j] as
// prime[j] [for example: let i = 5, j = 0, prime[j]
// = 2 [i*prime[j] = 10] so the smallest prime factor
// of '10' is '2' that is prime[j]] this loop runs
// only one time for numbers which are not prime
let j = 0;
while (j < prime.length && i * prime[j] < N && prime[j] <= SPF[i]) {
isprime[i * prime[j]] = false;
// put the smallest prime factor of i*prime[j]
SPF[i * prime[j]] = prime[j];
j++;
}
}
}
// Driver program to test above function
const N = 13; // Must be less than MAX_SIZE
manipulated_seive(N);
// Print all prime numbers less than N
console.log(prime.join(' '));
// Contributed by adityasha4x71
Output
2 3 5 7 11
In above example the complexity of finding prime numbers in a range of 0 to N is O(N * log (log (N))).
What is Logarithmic Time Complexity? A Complete Tutorial
Logarithmic time complexity is denoted as O(log n). It is a measure of how the runtime of an algorithm scales as the input size increases. In this comprehensive tutorial. In this article, we will look in-depth into the Logarithmic Complexity. We will also do various comparisons between different logarithmic complexities, when and where such logarithmic complexities are used, several examples of logarithmic complexities, and much more. So let’s get started.
Table of Content
- What is a Logarithm?
- What is Complexity Analysis?
- What is Space Complexity?
- What is Time Complexity?
- How to measure complexities?
- What is a Logarithm?
- Different Types of Logarithmic Complexities
- Simple Log Complexity (Log a)
- Double Logarithm (log log N)
- N logarithm N (N * log N)
- logarithm^2 N (log^2 N)
- N^2 logarithm N (N^2 * log N)
- N^3 logarithm N (N^3 log N)
- logarithm √N (log √N)
- Examples To Demonstrate Logarithmic Time Complexity
- Practice Problems for Logarithmic Time Complexity
- Comparison of various Logarithmic Time Complexities
- Frequently Asked Questions(FAQ’s) on Logarithmic Time Complexity
- Conclusion
Contact Us