Scribd
Upload
111 views15 pages

Time Complexity - Part 1 - Java

The document discusses algorithms and their efficiency. It defines an algorithm as a finite sequence of instructions that each require a finite amount of time and effort. The efficiency of an algorithm is measured by the resources like time it consumes to solve a problem of size n. Running time is analyzed independently of hardware by measuring the number of elementary steps or operations performed. For example, a sum algorithm that adds all elements in an array is analyzed to take O(n) time, where n is the number of elements in the array, as its running time grows linearly with the input size n.

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
111 views15 pages

Time Complexity - Part 1 - Java

The document discusses algorithms and their efficiency. It defines an algorithm as a finite sequence of instructions that each require a finite amount of time and effort. The efficiency of an algorithm is measured by the resources like time it consumes to solve a problem of size n. Running time is analyzed independently of hardware by measuring the number of elementary steps or operations performed. For example, a sum algorithm that adds all elements in an array is analyzed to take O(n) time, where n is the number of elements in the array, as its running time grows linearly with the input size n.

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