C++
Foundation
with
Data
Structures
Topic:
Time
Complexity
,
Introduction
An
important
question
while
programming
is:
How
efficient
is
an
algorithm
or
piece
of
code?
Efficiency
covers
lots
of
resources,
including:
• CPU
(time)
usage
• memory
usage
• disk
usage
• network
usage
All
are
important
but
we
are
mostly
concerned
about
CPU
time.
Be
careful
to
differentiate
between:
1.
Performance:
how
much
time/memory/disk/etc.
is
actually
used
when
a
program
is
run.
This
depends
on
the
machine,
compiler,
etc.
as
well
as
the
code
we
write.
2.
Complexity:
how
do
the
resource
requirements
of
a
program
or
algorithm
scale,
i.e.
what
happens
as
the
size
of
the
problem
being
solved
by
the
code
gets
larger.
Complexity
affects
performance
but
not
vice-‐versa.
The
time
required
by
a
function/method
is
proportional
to
the
number
of
"basic
operations"
that
it
performs.
Here
are
some
examples
of
basic
operations:
• one
arithmetic
operation
(e.g.
a+b
/
a*b)
• one
assignment
(e.g.
int
x
=
5)
• one
condition/test
(e.g.
x
==
0)
• one
input
read
(e.g.
reading
a
variable
from
console)
• one
output
write
(e.g.
writing
a
variable
on
console)
Some
functions/methods
perform
the
same
number
of
operations
every
time
they
are
called.
For
example,
the
size
function/method
of
the
string
class
always
performs
just
one
operation:
return
number
of
Items;
the
number
of
operations
is
independent
of
the
size
of
the
string.
We
say
that
functions/methods
like
this
(that
always
perform
a
fixed
number
of
basic
operations)
require
constant
time.
Foundation
with
Data
Structures
Topic:
Time
Complexity
,
Introduction
An
important
question
while
programming
is:
How
efficient
is
an
algorithm
or
piece
of
code?
Efficiency
covers
lots
of
resources,
including:
• CPU
(time)
usage
• memory
usage
• disk
usage
• network
usage
All
are
important
but
we
are
mostly
concerned
about
CPU
time.
Be
careful
to
differentiate
between:
1.
Performance:
how
much
time/memory/disk/etc.
is
actually
used
when
a
program
is
run.
This
depends
on
the
machine,
compiler,
etc.
as
well
as
the
code
we
write.
2.
Complexity:
how
do
the
resource
requirements
of
a
program
or
algorithm
scale,
i.e.
what
happens
as
the
size
of
the
problem
being
solved
by
the
code
gets
larger.
Complexity
affects
performance
but
not
vice-‐versa.
The
time
required
by
a
function/method
is
proportional
to
the
number
of
"basic
operations"
that
it
performs.
Here
are
some
examples
of
basic
operations:
• one
arithmetic
operation
(e.g.
a+b
/
a*b)
• one
assignment
(e.g.
int
x
=
5)
• one
condition/test
(e.g.
x
==
0)
• one
input
read
(e.g.
reading
a
variable
from
console)
• one
output
write
(e.g.
writing
a
variable
on
console)
Some
functions/methods
perform
the
same
number
of
operations
every
time
they
are
called.
For
example,
the
size
function/method
of
the
string
class
always
performs
just
one
operation:
return
number
of
Items;
the
number
of
operations
is
independent
of
the
size
of
the
string.
We
say
that
functions/methods
like
this
(that
always
perform
a
fixed
number
of
basic
operations)
require
constant
time.
