Skip to main content

循环分析

Frequent Loops Complexity

O(1)

Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function.

// set of non-recursive and non-loop statements

For example swap() function has O(1) time complexity.

A loop or recursion that runs a constant number of times is also considered as O(1). For example the following loop is O(1):

// Here c is a constant
for (int i = 1; i <= c; i++) {
// some O(1) expressions
}

O(n)

Time complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. For example following functions have O(n) time complexity:

// Here c is a positive integer constant
for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}

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

O(n2)

Time complexity of nested loops is equal to the number of times the innermost statement is executed. For example the following sample loops have O(n2) time complexity:

for (int i = 1; i <=n; i += c) {
for (int j = 1; j <=n; j += c) {
// some O(1) expressions
}
}

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

For example Selection Sort and Insertion Sort have O(n2) time complexity.

O(logn)

Time complexity of a loop is considered as O(logn) if the loop variables is divided / multiplied by a constant amount.

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

Let us see mathematically how the first for-loop is O(logn). The series of i that we get in first for-loop is 1, c, c2, c3, … ck. If we put ck equals to n, we get k which is logcn.

In addition, Binary Search(refer iterative implementation) has O(logn) time complexity, see more at below links:

O(loglogn)

Time complexity of a loop is considered as O(nlogn) if the loop variables is reduced / increased exponentially by a constant amount.

// Here c is a constant greater than 1
for (int i = 2; i <=n; i = pow(i, c)) {
// some O(1) expressions
}
//Here fun is sqrt or cuberoot or any other constant root
for (int i = n; i > 1; i = fun(i)) {
// some O(1) expressions
}

FAQ

Consecutive Loops

Q: How to combine time complexities of consecutive loops?

When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.

for (int i = 1; i <=m; i += c) {
// some O(1) expressions
}
for (int i = 1; i <=n; i += c) {
// some O(1) expressions
}

Time complexity of above code is O(m) + O(n) which is O(m+n), If m == n, the time complexity becomes O(2n) which is O(n).

if-else Condition in Loops

Q: How to calculate time complexity when there are many if, else statements inside loops?

As discussed before, worst case time complexity is the most useful among best, average and worst. Therefore we need to consider worst case. We evaluate the situation when values in if-else conditions cause maximum number of statements to be executed.

For example consider the linear search function where we consider the case when element is present at the end or not present at all.

tip

When the code is too complex to consider all if-else cases, we can get an upper bound by ignoring if else and other complex control statements.

Example: let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is θ(m). Consider the following program fragment written in a C like language:

counter = 0;
for (i = 1; i < = n; i++) {
if (A[i] == 1)
counter++;
else {
f(counter);
counter = 0;
}
}

The complexity of this program fragment is ? (GATE-CS-2004)

(A) Ω(n2)
(B) Ω(nlogn) and O(n2)
(C) Θ(n)
(D) O(n)

Please note that inside the else condition, f() is called first, then counter is set to 0. Consider the following cases:

  • All 1s in A[]: Time taken is Θ(n) as only counter++ is executed n times.
  • All 0s in A[]: Time taken is Θ(n) as only f(0) is called n times
  • Half 1s, then half 0s: Time taken is Θ(n) as only f(n/2) is called once.

So, option (C) is correct.

Recursive Functions

Q: How to calculate time complexity of recursive functions?

Time complexity of a recursive function can be written as a mathematical recurrence relation. To calculate time complexity, we must know how to solve recurrences. See the below quiz:

The time complexity of the following C function is (assume n > 0)

int recursive (int n) {
if (n == 1) return (1);
else return (recursive (n-1) + recursive (n-1));
}

(A) O(n)
(B) O(nlogn)
(C) O(n2)
(D) O(2n)

Recurrence relation for the code: T(n) = 2T(n-1) + k. We can solve the recurrence using substitution method:

T(n) = 2T(n-1) + k
= 2(2T(n-2) + k) + k
= 2(2(2T(n-3) + k) + k) + k.....
= 2x + 2(1 + 2 +....+ 2x-1)k
When base condition is met, i.e. n=1, x=n-1
= 2n-1T(1) + k(2n)
= O(2n)

So, option (D) is correct.

Quiz

All (114) questions: Quiz on Analysis of Algorithms

Question 5

What is time complexity of fun()?

int fun(int n) {
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}

(A) Θ(n2)
(B) Θ(nlogn)
(C) Θ(n)
(D) Θ(nlognlogn)

(C), For a input integer n, the innermost statement of fun() is executed following times. n + n/2 + n/4 + ... 1 So time complexity T(n) can be written as T(n) = O(n + n/2 + n/4 + ... 1) = O(n) The value of count is also n + n/2 + n/4 + .. + 1

Question 6

What is time complexity of fun()?

int fun(int n) {
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j > 0; j--)
count = count + 1;
return count;
}

(A) Θ(n)
(B) Θ(n2)
(C) Θ(nlogn)
(D) Θ(nlognlogn)

(B), The time complexity can be calculated by counting number of times the expression count = count + 1; is executed. The expression is executed 0 + 1 + 2 + 3 + 4 + .... + (n-1) times. Time complexity = Θ(0 + 1 + 2 + 3 + .. + n-1) = Θ(n*(n-1)/2) = Θ(n2)

Question 16

What is the time complexity of the below function?

void fun(int n, int arr[]) {
int i = 0, j = 0;
for(; i < n; ++i) {
while(j < n && arr[i] < arr[j])
j++;
}
}

(A) Θ(n)
(B) Θ(n2)
(C) Θ(nlogn)
(D) Θ(n(logn)2)

(A), In the first look, the time complexity seems to be O(n2) due to two loops. But, please note that the variable j is not initialized for each value of variable i. So, the inner loop runs at most n times. Please observe the difference between the function given in question and the below function:

void fun(int n, int arr[]) {
int i = 0, j = 0;
for(; i < n; ++i) {
j = 0;
while(j < n && arr[i] < arr[j])
j++;
}
}

Question 30

Consider the following function:

int unknown(int n) {
int i, j, k = 0;
for (i = n/2; i <= n; i++)
for (j = 2; j <= n; j = j * 2)
k = k + n/2;
return k;
}

What is the returned value of the above function? (GATE CS 2013)

(A) Θ(n2)
(B) Θ(n2logn)
(C) Θ(n3)
(D) Θ(n3logn)

(B), The outer loop runs n/2 or Θ(n) times. The inner loop runs (logn) times (Note that j is multiplied by 2 in every iteration). So the statement "k = k + n/2;" runs Θ(nlogn) times. The statement increases value of k by n/2. So the value of k becomes n/2*Θ(nlogn) which is Θ((n2)logn).

Please note that the complexity of the program is Θ(nlogn).

Reference

  1. Analysis of Algorithms | Set 4 (Analysis of Loops) - GeeksforGeeks