**Problem Detail:**

The following code should have a run time of $O(N)$,

`int min = INTEGER.MAX_VALUE; int max = INTEGER.MIN_VALUE; for (int x : array) { if (x < min) min = x; if (x > min) max = x; } `

but what about the following code?

`int min = INTEGER.MAX_VALUE; int max = INTEGER.MIN_VALUE; for (int x : array) { if (x < min) min = x; } for (int x : array) { if (x > min) max = x; } `

###### Asked By : Anonymous Human

###### Answered By : Anjo

Its **O(N)**. 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)`

.

Question Source : http://cs.stackexchange.com/questions/63983

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback