Time Complexity for nested loops with half-size

user_8144490 0
Viewed 920
void function(int n)
{
    int count = 0;

    // outer loop 
    for (int i=n/2; i<=n; i++)

        // middle loop 
        for (int j=1; j+n/2<=n; j = j++)

            // inner loop executes log n times
            for (int k=1; k<=n; k = k * 2)
                count++;
}

I am doing some exercise, and can someone please help me to figure out the Big-Oh of the above algorithm? I understand that the inner most loop executes for log n times. What about the outermost loop and middle loop ? Would that also be log n or n/2 ?

nested-loops big-o time-complexity
1 Answers

Assuming your code with full indentation is this:

void function(int n)
{
int count = 0;

// outer loop 
for (int i=n/2; i<=n; i++){

    // middle loop 
    for (int j=1; j+n/2<=n; j++){
        // inner loop executes log n times
        for (int k=1; k<=n; k = k * 2){
            count++;
        }
    }
 }
}

The time complexity can be calculated as follows:

  1. The innermost loop executes (log n) times, so its complexity is O(log n).
  2. The middle loop with j as the loop variable executes n / 2 times, with the innermost loop executing, each time in its iteration. Therefore, the time complexity of the middle loop is (n / 2) * O(log n) = O(n * log n).
  3. Similarly, the outermost loop also executes (n / 2) times, with the middle loop executing completely in it each iteration. So, its time complexity will be (n / 2) * O(n * log n) = O(n * n * log n).

Hence, the overall time complexity will be O(n^2 * log n).

user_123681540
Related