Java Reference
In-Depth Information
k = k + i + j;
}
}
It is a constant time,
c
, for executing
k = k + i + j;
The outer loop executes
n
times. For each iteration in the outer loop, the inner loop is
executed
n
times. Thus, the time complexity for the loop is
O
(
n
2
)
T
(
n
)
=
(a constant
c
)*
n
*
n
=
An algorithm with the
O
(
n
2
) time complexity is called a
quadratic algorithm
and it
exhibits a quadratic growth rate. The quadratic algorithm grows quickly as the problem
size increases. If you double the input size, the time for the algorithm is quadrupled.
Algorithms with a nested loop are often quadratic.
quadratic time
Example 3
Consider the following loop:
for
(
int
i =
1
; i <= n; i++) {
for
(
int
j =
1
; j <= i; j++) {
k = k + i + j;
}
}
The outer loop executes
n
times. For
i
1, 2,
c
, the inner loop is executed one time,
two times, and
n
times. Thus, the time complexity for the loop is
=
T
(
n
)
=
c
+
2
c
+
3
c
+
4
c
+
...
+
nc
=
cn
(
n
+
1)/2
(
c
/2)
n
2
=
+
(
c
/2)
n
O
(
n
2
)
=
Example 4
Consider the following loop:
for
(
int
i =
1
; i <= n; i++) {
for
(
int
j =
1
; j <=
20
; j++) {
k = k + i + j;
}
}
The inner loop executes 20 times, and the outer loop
n
times. Therefore, the time com-
plexity for the loop is
T
(
n
)
=
20 *
c
*
n
=
O
(
n
)
Example 5
Consider the following sequences:
for
(
int
j =
1
; j <=
10
; j++) {
k = k +
4
;
}
for
(
int
i =
1
; i <= n; i++) {
Search WWH ::
Custom Search