Java Reference
In-Depth Information
The time complexity of a sequence of statements in an algorithm or program is the sum of the
statements' individual complexities. However, it is sufficient to take instead the largest of these
complexities. In general, if
S
1
,
S
2
, . . . ,
S
k
is a sequence of program segments, and if
g
i
is the growth-rate
function for segment
S
i
, the time complexity of the sequence would be O(max(
g
1
,
g
2
, . . . ,
g
k
)), which is
equivalent to max(O(
g
1
), O(
g
2
), . . . , O(
g
k
)).
The time complexity of the
if
statement
if
(
condition
)
S
1
else
S
2
is the sum of the complexity of the condition and the complexity of
S
1
or
S
2
, whichever is largest.
The time complexity of a loop is the complexity of its body times the number of times the body
executes. Thus, the complexity of a loop such as
for
i = 1
to
m
S
is O(
m
x
g
(
n
)), or
m
x
O(
g
(
n
)), where
g
(
n
) is the growth-rate function for
S
. Note that the loop
variable
i
in this example increments by 1. In the following loop,
i
is doubled at each iteration:
for
i = 1
to
m, i = 2 * i
S
The complexity of this loop is O(log(
m
)
x
g
(
n
)), or O(log(
m
))
x
O(
g
(
n
)).
Note:
The complexities of program constructs
Construct
Time Complexity
Consecutive program segments
S
1
,
S
2
, . . . ,
S
k
whose
growth-rate functions are
g
1
, . . . ,
g
k
, respectively
max(O(
g
1
), O(
g
2
), . . . , O(
g
k
))
An
if
statement that chooses between program segments
S
1
and
S
2
whose growth-rate functions are
g
1
and
g
2
,
respectively
O(
condition
) + max(O(
g
1
), O(
g
2
))
A loop that iterates
m
times and has a body whose
growth-rate function is
g
m
x
O(
g
(
n
))
