Time
Java
Complexity
Part 2
Hira Awais
Lecturer (DCS)
Slide courtesy : Dr. Zahid Halim
Big-Oh Notation
Even though it is correct to say “7n - 3 is O(n3)”, a
better statement is “7n - 3 is O(n)”, that is, one
should make the approximation as tight as
possible
Simple Rule:
Drop lower order terms and constant factors
7n-3 is O(n)
8n2log n + 5n2 + n is O(n2log n)
Performance Classification
f(n) Classification
1 Constant: run time is fixed, and does not depend upon n. Most instructions are executed once, or only a few times,
regardless of the amount of information being processed
log n Logarithmic: when n increases, so does run time, but much slower. Common in programs which solve large problems
by transforming them into smaller problems.
n Linear: run time varies directly with n. Typically, a small amount of processing is done on each element.
n log n When n doubles, run time slightly more than doubles. Common in programs which break a problem down into
smaller sub-problems, solves them independently, then combines solutions
n2 Quadratic: when n doubles, runtime increases fourfold. Practical only for small problems; typically the program
processes all pairs of input (e.g. in a double nested loop).
n3 Cubic: when n doubles, runtime increases eightfold
2n Exponential: when n doubles, run time squares. This is often the result of a natural, “brute force” solution.
Size does matter
What happens if we double the input size N?
N log2N 5N N log2N N2 2N
8 3 40 24 64 256
16 4 80 64 256 65536
32 5 160 160 1024 ~109
64 6 320 384 4096 ~1019
128 7 640 896 16384 ~1038
256 8 1280 2048 65536 ~1076
Size does matter
Suppose a program has run time O(n!) and the run
time for
n = 10 is 1 second
For n = 12, the run time is 2 minutes
For n = 14, the run time is 6 hours
For n = 16, the run time is 2 months
For n = 18, the run time is 50 years
For n = 20, the run time is 200 centuries
Standard Analysis Techniques
Constant time statements
Analysing Loops
Analysing Nested Loops
Analysing Sequence of Statements
Analysing Conditional Statements
Constant time statements
Simplest case: O(1) time statements
Assignment statements of simple data types
int x = y;
Arithmetic operations:
x = 5 * y + 4 - z;
Array referencing:
A[j] = 5;
Array assignment:
j, A[j] = 5;
Most conditional tests:
if (x < 12) ...
Analysing Loops
Any loop has two parts:
How many iterations are performed?
How many steps per iteration?
int sum = 0,j;
for (j=0; j < N; j++)
sum = sum +j;
Loop executes N times (0..N-1)
4 = O(1) steps per iteration
Total time is N * O(1) = O(N*1) = O(N)
Analysing Loops
What about this for loop?
int sum =0, j;
for (j=0; j < 100; j++)
sum = sum +j;
Loop executes 100 times
4 = O(1) steps per iteration
Total time is 100 * O(1) = O(100 * 1) = O(100) =
O(1)
Analysing Nested Loops
Treat just like a single loop and evaluate each level of
nesting as needed:
int j,k;
for (j=0; j<N; j++)
for (k=N; k>0; k--)
sum += k+j;
Start with outer loop:
How many iterations? N
How much time per iteration? Need to evaluate inner
loop
Inner loop uses O(N) time
Total time is N * O(N) = O(N*N) = O(N2)
Analysing Nested Loops
Whatif the number of iterations of one loop
depends on the counter of the other?
int j,k;
for (j=0; j < N; j++)
for (k=0; k < j; k++)
sum += k+j;
Analyze inner and outer loop together:
Number of iterations of the inner loop is:
0 + 1 + 2 + ... + (N-1) = O(N2)
Analysing Sequence of
Statements
For
a sequence of statements, compute their
complexity functions individually and add them up
for (j=0; j < N; j++)
for (k =0; k < j; k++)
sum = sum + j*k;
for (l=0; l < N; l++)
sum = sum -l;
cout<<“Sum=”<<sum;
Total cost is O(N2) + O(N) +O(1) = O(N2)
SUM RULE
Analysing Conditional
Statements
What about conditional statements such as
if (condition)
statement1;
else
statement2;
where statement1 runs in O(N) time and statement2
runs in O(N2) time?
We use "worst case" complexity: among all inputs of
size N, that is the maximum running time?
The analysis for the example above is O(N2)
Time complexity familiar tasks
Growth rate
Task
O(N2)
Matrix/vector multiply
Getting a specific element from a list
O(1)
Dividing a list in half, dividing one halve in half, O(log2N)
etc O(log2N)
Binary Search O(N)
Scanning (brute force search) a list
O(Nk)
Nested for loops (k levels)
O(N log2N)
MergeSort
BubbleSort O(N2)
Generate all subsets of a set of data O(2N)
Generate all permutations of a set of data O(N!)