Design and analysis of algorithm lecture 3 .ppt

Design and analysis of algorithm lecture 3

1. Design & Analysis Algorithms
Lecture # 03
Instructor: Yasmeen

2. Understanding time & space complexity

3. Understanding time & space
complexity
Time complexity refers to how long an
algorithm takes to complete based on the input
size (n).
If n increases, how does the execution time
change? This is what Time Complexity
measures!

4. Basic Time Complexities- Big-O
Notation
Complexity Meaning Real-Life Example
O(1) Constant Time
Checking only one shelf
in a cupboard
O(n) Linear Time
Checking all shelves in
a cupboard
O(log n) Logarithmic Time
Searching a word in a
dictionary by starting
from the middle
O(n²) Quadratic Time
Checking every item
inside every shelf

5. O(1) - Constant Time Complexity
O(1) or Constant Time Complexity means
that no matter the input size, the algorithm or
operation always completes in the same
amount of time.
Example of O(1)
If you have an array and only access the first
element, this operation is O(1).
Continue

6. O(1) - Constant Time Complexity
1.Start
2.Declare an integer array with
some predefined elements.
3.Access the first element of the
array using arr[0].
4.Print the first element.
5.End

7. O(1) - Constant Time Complexity
#include <iostream>
using namespace std;
int main() {
 int arr[] = {10, 20, 30, 40, 50};
 cout << arr[0]; // This always executes in a
single step (O(1))
 return 0;
}

8. O(1) - Constant Time Complexity
Explanation:
Whether the array has 5 elements or 5
million, accessing arr[0] is always one
operation.
That’s why its time complexity is O(1).

9. Practice Questions
Q. Print first and last element of an array?
Q. Find array size without sizeof?
Q. Get element from user-specified index
with validation?
Q. Print array in reverse order?
Q. Calculate sum and average of array
elements?

10. O(n) – Linear Time Complexity
If the execution time of an algorithm directly
depends on the input size n, then its time
complexity is O(n).
If the input size doubles (2x), the execution
time also doubles (2x).
If the input size triples (3x), the execution
time also triples (3x).

11. Example (Printing All Elements of
an Array)
1.Start
2.Declare an integer array arr with
values {10, 20, 30, 40, 50}.
3.Initialize a loop variable i = 0.
4.Repeat steps 5-6 while i < 5:
Print arr[i] followed by a space.
Increment i by 1.
5.End loop.
6.Stop

12. Example (Printing All Elements of
an Array)
print all elements of an array, you must
access each element one by one.
#include <iostream>
using namespace std;
int main() { // Main function where program execution starts.

int arr[] = {10, 20, 30, 40, 50}; // Declares an integer array 'arr' with 5 elements.
for (int i = 0; i < 5; i++) { // A for loop that iterates through the array elements.
cout << arr[i] << " "; // Prints the current element of the array followed by a space.
}
return 0; // Indicates successful termination of the program.
}

13. Example (Printing All Elements of
an Array)
Output:
10 20 30 40 50

14. Practice question
1.Modify the Loop Condition
2.Print Array in Reverse Order
3.Find the Sum of All Array Elements
4.Find the Largest Element in the ArrayCount
5.Even and Odd Numbers in the Array

15. O(log n) – Logarithmic Time Complexity
Logarithmic time complexity occurs when the data
halves in each step.
This means the input size n becomes:
n/2 in the first step
n/4 in the second step
n/8 in the third step
Since the dataset is shrinking so quickly, O(log n)
algorithms are extremely fast. The best example
is binary search.

16. Example 1: Book Search in a
Library
Imagine you have 100 books, and you need to find a specific one.
If you use binary search, the process will be:
1.Step 1: Check the middle book of 100.
If it's not the book you're looking for, ignore
➡️
half (now 50 books remain).
2.Step 2: Check the middle book of 50.
If it's not the book, ignore
➡️
half (now 25 books remain).
3.Step 3: Check the middle book of 25.
If it's not the book, ignore
➡️
half (now 12 books remain).
This process continues, removing half in each step until you find the book.
 In just 7 steps, you can find a book in 100 books!
How many steps for larger data?
100 books → 7 steps
1,000 books → 10 steps
1,000,000 books → 20 steps
Even with millions of books, the search remains super fast!

17. Example 2: Binary Search (O(log n))
Index: 0 1 2 3 4
Array: [10, 20, 30, 40, 50]
We need to find 40 using binary search:
1Step 1: Check mid = 30 (not found, move right).
2 Step 2: Check mid = 40 (found ✅).
??????

Only 2 steps!
??????
??????

Linear search would take 5 steps, but binary search does it in just 2!
Why is O(log n) fast?
Even with huge data, the number of steps remains small.
That’s why O(log n) algorithms like binary search are much faster than O(n)
linear searches

18. O(n) vs O(log n) Comparison
Input Size (n) O(n) (Linear) O(log n) (Logarithmic)
10 10 steps 3 steps
100 100 steps 6 steps
1000 1000 steps 10 steps
1,000,000 1,000,000 steps 20 steps

19. Binary Search Algorithm (O(log n))
1.1Start with a sorted array
2.2Initialize: low = 0, high = n - 1
3.3 Loop while low <= high:
•Find mid = (low + high) / 2
•If arr[mid] == target, return index found
•If arr[mid] < target, move low = mid + 1 (ignore
left half)
•Else, move high = mid - 1 (ignore right half)
4.If loop ends, element not found

20. Algorithm vs Program
#include <iostream> // Include input-output library
using namespace std;
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70}, // Sorted array
n = 7, // Size of the array
target = 40, // Target element to search
low = 0, high = n - 1; // Pointers for binary search
while (low <= high) { // Run loop while search range is valid
int mid = (low + high) / 2; // Find the middle index
if (arr[mid] == target) // If target is found
return cout << "Found", 0; // Print result and exit
(arr[mid] < target) ? low = mid + 1 : high = mid - 1; // Move right if target is
greater, else move left
}
cout << "Not Found"; // If loop ends, element is not in the array
}

21. O(n²) – Quadratic Time Complexity
What is Quadratic Time Complexity? (O(n²))
Quadratic time complexity means that as the input size (n)
increases, the number of operations grows proportionally
to n².
Mathematical Representation:
If n = 10, then 10 × 10 = 100 operations
If n = 100, then 100 × 100 = 10,000 operations
O(n²) algorithms generally involve nested loops (a
loop inside another loop).

22. Examples of O(n²) Algorithms
Bubble Sort
Selection Sort
Insertion Sort
Checking duplicate elements in an
array (using nested loops)

23. Algorithm (Step-by-Step)
1Start
2nput n (size of input)
3Outer loop runs n times
4Inner loop also runs n times
5Print (i, j) values in each iteration
6End

24. cont
2.#include <iostream>
3.using namespace std;
4.int main() {
5. int n = 3; //
?????? Input size
6. for (int i = 0; i < n; i++) { //
?????? Outer loop (n times)
7. for (int j = 0; j < n; j++) { //
?????? Inner loop (n times)
8. cout << i << "," << j << " "; // Print indices
9. }
10. cout << endl;
11. }
12.}

25. Space Complexity
Introduction to Space Complexity Space complexity
refers to the amount of extra memory required for an
algorithm to run. It measures memory usage based on
input size.
Space Complexity Formula Total memory usage =
Fixed Space + Extra Space
Fixed Space (Constant Space, O(1)) → Memory that remains
the same regardless of input size. (e.g., variables, constants)
Extra Space (Variable Space, O(n)) → Memory that changes
with input size. (e.g., arrays, recursion stack)

26. Types of Space Complexity
#include <iostream> // Including the input-output stream library
using namespace std; // Using the standard namespace
// Function to calculate the sum of two numbers
int sum(int a, int b) {
 return a + b; // Returning the sum of a and b
}
int main() {
 int x = 5, y = 10; // Declaring and initializing two integer variables
 cout << "Sum: " << sum(x, y) << endl; // Calling the sum function and printing the
result
 return 0; // Returning 0 to indicate successful execution
}

27. Types of Space Complexity
Analysis:
The program uses only 2 variables (a, b).
Memory usage remains the same regardless of
input size.
Space Complexity = O(1) (Constant Space)

28. Types of Space Complexity
#include <iostream> // Includes the input-output stream library
using namespace std; // Using the standard namespace to avoid writing std:: before functions
// Function to create an array and print its elements
void printArray(int n) {
int arr[n]; //
?????? Creates an array of size `n`, which results in O(n) space complexity
// Loop to initialize and print array elements
for (int i = 0; i < n; i++) {
arr[i] = i; // Assigns the index value to each array element
cout << arr[i] << " "; // Prints the array element
}
}
// Main function: Program execution starts here
int main() {
printArray(5); // Calls the function with `n = 5`
}

29. Types of Space Complexity
Analysis:
Each function call uses stack memory.
If n = 5, then 5 function calls will be stored in memory.
Space Complexity = O(n) (Recursion Stack Space)