Logarithmic Time Complexity O(Log n)

Logarithmic Time Complexity O(Log Log n):

The time Complexity of a loop is considered as O(Logn) if the loop variables are divided/multiplied by a constant amount. And also for recursive calls in the recursive function, the Time Complexity is considered as O(Logn).

C++

for (int i = 1; i <= n; i *= c) {
    // some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
    // some O(1) expressions
}
 
// This code is contributed by Kshitij

C

for (int i = 1; i <= n; i *= c) {
    // some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
    // some O(1) expressions
}

Java

for (int i = 1; i <= n; i *= c) {
    // some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
    // some O(1) expressions
}
 
// This code is contributed by Utkarsh

C#

using System;
 
class Program {
    static void Main(string[] args)
    {
        int n = 10; // assuming n is some integer value
        int c = 2; // assuming c is some integer value
 
        // Loop to iterate through powers of c up to n
        for (int i = 1; i <= n; i *= c) {
            // O(1) expressions here
            Console.WriteLine("i = " + i);
        }
 
        // Loop to iterate through powers of c down from n
        for (int i = n; i > 0; i /= c) {
            // O(1) expressions here
            Console.WriteLine("i = " + i);
        }
    }
}

Javascript

for (var i = 1; i <= n; i *= c) {
    // some O(1) expressions
}
for (var i = n; i > 0; i /= c) {
    // some O(1) expressions
}

Python3

i = 1
while(i <= n):
    # some O(1) expressions
    i = i*c
 
i = n
while(i > 0):
    # some O(1) expressions
    i = i//c
 
# This code is contributed by Pushpesh Raj

C++

// Recursive function
void recurse(int n)
{
    if (n <= 0)
        return;
    else {
        // some O(1) expressions
    }
    recurse(n/c);
  // Here c is positive integer constant greater than 1
}
// This code is contributed by Kshitij

C

// Recursive function
void recurse(int n)
{
    if (n <= 0)
        return;
    else {
        // some O(1) expressions
    }
    recurse(n/c);
  // Here c is positive integer constant greater than 1
}

Java

// Recursive function
void recurse(int n)
{
    if (n <= 0)
        return;
    else {
        // some O(1) expressions
    }
    recurse(n/c);
  // Here c is positive integer constant greater than 1
 
}
// This code is contributed by Utkarsh

C#

using System;
 
class Program {
    // Recursive function
    static void Recurse(int n, int c)
    {
        // Base case: If n is less than or equal to 0,
        // return
        if (n <= 0)
            return;
        else {
            // Perform some O(1) expressions
 
            // Recursive call with updated parameter (n/c)
            Recurse(n / c, c);
        }
    }
 
    static void Main()
    {
        int n = 10; // Example value for n
        int c = 2; // Example value for c
 
        // Function Call
        Recurse(n, c);
 
        Console.WriteLine("Recursive function executed.");
    }
}

Javascript

// Recursive function
function recurse(n)
{
    if (n <= 0)
        return;
    else {
        // some O(1) expressions
    }
    recurse(n/c);
 // Here c is positive integer constant greater than 1
}

Python3

# Recursive function
def recurse(n):
    if(n <= 0):
        return
    else:
        # some O(1) expressions
    recurse(n/c)
# Here c is positive integer constant greater than 1
# This code is contributed by Pushpesh Raj

Example: Binary Search(refer iterative implementation) has O(Logn) time complexity.

How to Analyse Loops for Complexity Analysis of Algorithms

We have discussed Asymptotic Analysis, Worst, Average and Best Cases and Asymptotic Notations in previous posts. In this post, an analysis of iterative programs with simple examples is discussed.

The analysis of loops for the complexity analysis of algorithms involves finding the number of operations performed by a loop as a function of the input size. This is usually done by determining the number of iterations of the loop and the number of operations performed in each iteration.

Here are the general steps to analyze loops for complexity analysis:

Determine the number of iterations of the loop. This is usually done by analyzing the loop control variables and the loop termination condition.

Determine the number of operations performed in each iteration of the loop. This can include both arithmetic operations and data access operations, such as array accesses or memory accesses.

Express the total number of operations performed by the loop as a function of the input size. This may involve using mathematical expressions or finding a closed-form expression for the number of operations performed by the loop.

Determine the order of growth of the expression for the number of operations performed by the loop. This can be done by using techniques such as big O notation or by finding the dominant term and ignoring lower-order terms.

Logarithmic Time Complexity O(Log n)

C++

C

Java

C#

Javascript

Python3

C++

C

Java

C#

Javascript

Python3

How to Analyse Loops for Complexity Analysis of Algorithms

Similar Reads

Contact Us