Java
Part 2
Hira Awais
Lecturer (DCS)
DDSA (FOC)
Slide courtesy : Dr. Zahid Halim
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)
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.
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
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
Constant time statements
Analysing Loops
Analysing Nested Loops
Analysing Sequence of Statements
Analysing Conditional 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) ...
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)
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)
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)
What if 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)
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
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)
Growth rate
Task
Matrix/vector multiply O(N2)
Getting a specific element from a list O(1)
Dividing a list in half, dividing one halve in half, etc O(log2N)
Binary Search O(log2N)
Scanning (brute force search) a list O(N)
Nested for loops (k levels) O(Nk)
MergeSort O(N log2N)
BubbleSort O(N2)
Generate all subsets of a set of data
O(2N)
Generate all permutations of a set of data
O(N!)
