# How to determine Time Complexity | Techbirds

**Posted on:**September 5, 2017 /

**Categories: Mobile Applications**

**Posted on:** December 18, 2013 /

**Categories: Tutorials** / **Author Name:** Md. Sadiq Ali

In general, how can you determine the running time of a piece of code? The answer is that it depends on what kinds of statements are used.

### 1. Sequence of statements

statement 1; statement 2; … statement k; The total time is found by adding the times for all statements:

total time = time(statement 1) + time(statement 2) + … + time(statement k)

If each statement is “simple” (only involves basic operations) then the time for each statement is constant and the total time is also constant: **O(1)**.

### 2. if-then-else statements

if (condition) { sequence of statements 1 } else { sequence of statements 2 }

Here, either sequence 1 will execute, or sequence 2 will execute. Therefore, the worst-case time is the slowest of the two possibilities: max(time(sequence 1), time(sequence 2)). For example, if sequence 1 is O(N) and sequence 2 is O(1) the worst-case time for the whole if-then-else statement would be **O(N)**.

### 3. for loops

for (i = 0; i < N; i++) { sequence of statements }

The loop executes N times, so the sequence of statements also executes N times. Since we assume the statements are O(1), the total time for the for loop is **N * O(1)**, which is **O(N)** overall.

### 4. Nested loops

First we’ll consider loops where the number of iterations of the inner loop is independent of the value of the outer loop’s index. For example:

for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { sequence of statements } }

The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the complexity is **O(N * M)**.

In a common special case where the stopping condition of the inner loop is j < N instead of j < M (i.e., the inner loop also executes N times), the total complexity for the two loops is **O(N ^{2})**.

Now let’s consider nested loops where the number of iterations of the inner loop depends on the value of the outer loop’s index. For example:

for (i = 0; i < N; i++) { for (j = i+1; j < N; j++) { sequence of statements } } Now we can’t just multiply the number of iterations of the outer loop times the number of iterations of the inner loop, because the inner loop has a different number of iterations each time. So let’s think about how many iterations that inner loop has. That information is given in the following table: Value of i Number of iterations of inner loop 0 N 1 N-1 2 N-2 … … N-2 2

N-1 1

So we can see that the total number of times the sequence of statements executes is: N + N-1 + N-2 + … + 3 + 2 + 1. We’ve seen that formula before: the total is **O(N ^{2})**.

for more info click here.

Enjoy…

412 total views, 2 views today

Share this On