Scribd
Upload
35 views15 pages

Lecture 02 - Time Complexity

- The document discusses time complexity and Big O notation for analyzing algorithms - It provides examples of common time complexities like O(1), O(log N), O(N), O(N^2), and O(2^N) - The document explains that Big O notation expresses the fastest growing component of time as input size increases, ignoring lower order terms - Examples are provided to demonstrate calculating the time complexity of different algorithms in Big O notation

Uploaded by

Qura tul Ain
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
35 views15 pages

Lecture 02 - Time Complexity

- The document discusses time complexity and Big O notation for analyzing algorithms - It provides examples of common time complexities like O(1), O(log N), O(N), O(N^2), and O(2^N) - The document explains that Big O notation expresses the fastest growing component of time as input size increases, ignoring lower order terms - Examples are provided to demonstrate calculating the time complexity of different algorithms in Big O notation

Uploaded by

Qura tul Ain
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

Material adapted from: ECE250, Waterloo

CS2001 – DATA STRUCTURES

Lecture # 02
August 28, 2023 Dr. Rabia Maqsood
Fall 2023 [email protected]
FAST – NUCES, CFD Campus
TODAY’S TOPICS
q Time Complexity
q Big-O notation

CS 2001 - FALL 2023 2


WHY ANALYSIS OF ALGORITHMS?
Analyzing an algorithm means to predict the resources that the algorithm
requires.

It includes memory, communication bandwidth, computer hardware and


some others.

But more important is the computational time.

CS 2001 - FALL 2023 3


WHY ANALYSIS OF ALGORITHMS?
Suppose we have two algorithms; how can we tell which is better?

Option 1: we could implement both algorithms, run them both & compute
execution time
­ How?
­ Any issue with this approach?
­ Expensive and error prone, machine & compiler dependent

Option 2: preferably, we should analyze them mathematically


­ Perform algorithm analysis using asymptotic complexity
­ Calculate the no. of (primitive) operations to be performed

CS 2001 - FALL 2023 4


AYSMPTOTIC COMPLEXITY
Evaluate the performance of an algorithm in terms of input size
­ Focus is not to calculate the actual execution time, but how the time (or space) taken by an algorithm
increases with the input size

Example: write N elements in an array to a file


Algorithm: write an array to a file

Open the file


While more elements in array do
write the next element

(N * time-to-write-one-element) + time-to-open-the-file

CS 2001 - FALL 2023 5


BIG-O NOTATION
Big-O or order of magnitude: expresses computing time (complexity) as the term in a
function that increases more rapidly relative to the size of a problem

For example: f(N) = N4 + 2000N2 + 50N + 100


f(N) is order of N4 or in Big-O notation, O(N4)

Lower terms become insignificant as the N or size of the input increases!

CS 2001 - FALL 2023 6


AYSMPTOTIC COMPLEXITY
Evaluate the performance of an algorithm in terms of input size
­ Focus is not to calculate the actual execution time, but how the time (or space) taken by an algorithm
increases with the input size

Example: write N elements in an array to a file


Algorithm: write an array to a file

Open the file Now, what is the time


While more elements in array do complexity in Big-O notation?
write the next element

(N * time-to-write-one-element) + time-to-open-the-file

CS 2001 - FALL 2023 7


COMMON ORDERS OF MAGNITUDE
Notation Meaning

O(1) Constant time

O(log2N) Logarithmic time

O(N) Linear time

O(N log2N) -

O(N2) Quadratic time

(O2N) Expoential time


By Cmglee (Own work) [CC BY-SA 4.0],
via Wikimedia Commons

CS 2001 - FALL 2023 8


COMMON ORDERS OF MAGNITUDE

CS 2001 - FALL 2023 9


EXAMPLE
Compute the time complexity of the given algorithm.

if (condition) {
sequence of statements 1
}
else {
sequence of statements 2
}

CS 2001 - FALL 2023 10


EXAMPLE
Compute the time complexity of the given algorithm.

int find_max( int *array, int n ) {


int max = array[0];

for ( int i = 1; i < n; ++i ) {


if ( array[i] > max ) {
max = array[i];
}
}

return max;
}

CS 2001 - FALL 2023 11


EXAMPLE
Compute the time complexity for the given algorithm.

for (i = 0; i < N; i++) {


for (j = 0; j < N; j++) {
statement1
}
}

for (k = 0; k < N; k++) {


statement1
statement2
}

CS 2001 - FALL 2023 12


QUESTION?
Does the time complexity depends on the number of lines of code?

CS 2001 - FALL 2023 13


EXAMPLE

What is the time complexity in Big-O?

CS 2001 - FALL 2023 14


READING MATERIAL
Nell Dale: Chapter 3
An article: https://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

CS 2001 - FALL 2023 15

You might also like