Scribd
Upload
31 views

Time Complexity - Part 3 - Java

The document discusses algorithm analysis and Big O notation. It provides examples of common algorithms and their time complexities including: - Linear time: O(n) - Logarithmic time: O(log n) - Quadratic time: O(n^2) - Cubic time: O(n^3) - Exponential time: O(c^n) It also discusses analyzing loops and nested loops, sequences of statements, and conditional statements to determine overall time complexity.

Uploaded by

onlineearningfor
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views

Time Complexity - Part 3 - Java

The document discusses algorithm analysis and Big O notation. It provides examples of common algorithms and their time complexities including: - Linear time: O(n) - Logarithmic time: O(log n) - Quadratic time: O(n^2) - Cubic time: O(n^3) - Exponential time: O(c^n) It also discusses analyzing loops and nested loops, sequences of statements, and conditional statements to determine overall time complexity.

Uploaded by

onlineearningfor
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

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!)

You might also like