Time Complexity - Part 1 - Java

Download as pdf or txt
Download as pdf or txt
You are on page 1of 15

Java

Part 1

Hira Awais
Lecturer (DCS)
DDSA (FOC)
 Slide courtesy : Dr. Zahid Halim
• Finite sequence of instructions.

• Each instruction having a clear meaning.

• Each instruction requiring finite amount of effort.

• Each instruction requiring finite time to complete


• Finite sequence of instructions.
 An input should not take the program in an infinite loop
• Each instruction having a clear meaning.
 Very subjective. What is clear to me, may not be clear to you.
• Each instruction requiring finite amount of effort.
 Very subjective. Finite on a super computer or a P4?

• Each instruction requiringfinite time to complete.


 Very subjective. 1 min, 1 hr, 1 year or a lifetime?
A finite set of statements that guarantees an optimal solution in
finite interval of time
 Run in less time
 Consume less memory

But computational resources (time complexity) is usually


more important
 The efficiency of an algorithm is a measure of the amount of
resources consumed in solving a problem of size n.
▪ The resource we are most interested in is time
▪ We can use the same techniques to analyze the consumption
of other resources, such as memory space.
 It would seem that the most obvious way to measure the
efficiency of an algorithm is to run it and measure how much
processor time is needed
 Is it correct
 Hardware
 Operating System
 Compiler
 Size of input
 Nature of Input
 Algorithm

Which should be improved?


 Depends upon
▪ Input Size
▪ Nature of Input
 Generally time grows with size of input, so running time of an
algorithm is usually measured as function of input size.
 Running time is measured in terms of number of
steps/primitive operations performed
 Independent from machine, OS
 Running time is measured by number of steps/primitive
operations performed
 Steps means elementary operation like
 ,+, *,<, =, A[i] etc
 We will measure number of steps taken in term of size of
input
// Input: int A[N], array of N integers
// Output: Sum of all numbers in array A
int Sum(int[] A, int N)
{
1. int s=0;
2. for (int i=0; i< N; i++)
3. s = s + A[i];
4. return s;
}
How should we analyse this?
// Input: int A[N], array of N integers
// Output: Sum of all numbers in array A

1,2,8: Once
3,4,5,6,7: Once per each iteration
of for loop, N iteration
Total: 5N + 3
The complexity function of the
algorithm is : f(N) = 5N +3
Estimated running time for different values of N:

N = 10 => 53 steps
N = 100 => 503 steps
N = 1,000 => 5003 steps
N = 1,000,000 => 5,000,003 steps

As N grows, the number of steps grow in linear proportion to


N for this function “Sum”
What about the +3 and 5 in 5N+3?
 As N gets large, the +3 becomes insignificant
 5 is inaccurate, as different operations require varying
amounts of time and also does not have any significant
importance
What is fundamental is that the time is linear in N.
Asymptotic Complexity: As N gets large, concentrate on the
highest order term:
 Drop lower order terms such as +3
 Drop the constant coefficient of the highest order term i.e. N
Performance: how much time/memory/disk/... is actually used
when a program is run. This depends on the machine,
compiler, etc. as well as the code.

Complexity: how do the resource requirements of a program or


algorithm scale, i.e., what happens as the size of the problem
being solved gets larger.

You might also like