Practical:- 1
Algorithms
An algorithm is a precise sequence of steps designed to accomplish a specific task. Essential
characteristics of an algorithm include:
● Input: Zero or more defined inputs are supplied to the algorithm.
● Output: One or more outputs are produced that relate directly to the given inputs.
● Definiteness: Each step is unambiguous and clearly specified.
● Finiteness: The algorithm consistently terminates after a finite number of steps.
● Effectiveness: Each operation can be executed precisely and within a finite time frame.
Example: Calculating Factorial
● Step 1: Receive a number n as input.
● Step 2: Initialize a variable 'result' to 1.
● Step 3: Multiply 'result' by n and store the result back in 'result'.
● Step 4: Decrease n by 1.
● Step 5: If n is greater than 0, go back to step 3.
● Step 6: Output the value of 'result'.
Algorithm Analysis
Algorithm analysis primarily focuses on time complexity and space complexity.
● Time Complexity: This measures how an algorithm's execution time grows relative to
the input size. It's often expressed using Big O notation.
● Types of Time Complexity Analysis:
○ Best Case: Identifies the input that yields the shortest execution time.
○ Worst Case: Determines the input that results in the longest execution time.
○ Average Case: Calculates the expected execution time based on all possible
inputs.
Time Complexity Notation
● Big O Notation (O): Represents the upper bound of an algorithm's growth rate. It
provides an asymptotic upper limit on the running time.
● Big Omega Notation (Ω): Indicates the lower bound of an algorithm's growth rate. It
establishes an asymptotic lower limit on the running time.
● Big Theta Notation (Θ): Specifies a tight bound on the algorithm's growth rate,
encompassing both upper and lower limits.
Practical:- 2
C++ Program to Find Sum of First N Natural Numbers
C++
#include <iostream>
using namespace std;
int main() {
int n, sum = 0;
cout << "Enter a positive integer: ";
cin >> n;
for (int i = 1; i <= n; ++i) {
sum += i;
cout << "The sum of first " << n << " natural numbers is " << sum << endl;
return 0;}
output-
Enter a positive integer: 5
The sum of first 5 natural numbers is 15
Time Complexity:
● The loop iterates n times, performing a constant-time addition operation in each iteration.
● Therefore, the total time complexity is O(n), linear with respect to the input size n.
Space Complexity:
● The algorithm uses constant extra space for variables sum and i, regardless of the input
size.
● Thus, the space complexity is O(1), constant.
Here's the step-by-step calculation for the time and space complexity of the program:
Time Complexity
1. Input and Initialization:
○ int n, sum = 0;
○ Time taken: O(1)O(1)O(1) (constant time)
2. Reading the Input:
○ cin >> n;
○ Time taken: O(1)O(1)O(1)
3. Loop Execution:
○ for (int i = 1; i <= n; ++i)
■ This loop runs nnn times.
4. Inside the Loop:
○ sum += i;
○ Time taken per iteration: O(1)O(1)O(1)
5. Output the Result:
○ cout << "The sum of first " << n << " natural numbers is "
<< sum << endl;
○ Time taken: O(1)O(1)O(1)
Total Time Complexity:
● Initial setup and input reading: O(1)O(1)O(1)
● Loop: n×O(1)=O(n)n \times O(1) = O(n)n×O(1)=O(n)
● Output: O(1)O(1)O(1)
Thus, the overall time complexity is: O(1)+O(n)+O(1)=O(n)O(1) + O(n) + O(1) =
O(n)O(1)+O(n)+O(1)=O(n)
Space Complexity
1. Variables:
○ int n: Takes constant space O(1)O(1)O(1)
○ int sum: Takes constant space O(1)O(1)O(1)
2. Loop Variable:
○ int i: Takes constant space O(1)O(1)O(1)
Total Space Complexity:
● All variables and loop variable: O(1)+O(1)+O(1)=O(1)O(1) + O(1) + O(1) =
O(1)O(1)+O(1)+O(1)=O(1)
Thus, the overall space complexity is O(1)O(1)O(1).
Step Operation Time Space
Complexity Complexity
Variable int n, sum O(1) O(1)
= 0;
Declaration
Input Reading cin >> n; O(1) O(1)
Loop for (int i O(n) O(1)
Initialization = 1; i <=
n; ++i)
Loop Body sum += i; O(1)per O(1)
iteration
Output cout << O(1) O(1)
"The sum
of first "
<< n << "
... ;
Total O(n) O(1)
Practical:- 3
C++ Program to Find Sum of First N Natural Numbers
Using Recursion
#include <iostream>
using namespace std;
int sum_of_n(int n) {
if (n == 0) {
return 0;
else {
return n + sum_of_n(n - 1);
int main() {
int n;
cout << "Enter a positive integer: ";
cin >> n;
int result = sum_of_n(n);
cout << "The sum of first " << n << " natural numbers is " << result << endl;
return 0;
output-
Enter a positive integer: 5
The sum of first 5 natural numbers is 15
Time Complexity:
● The recursive function makes n recursive calls.
● In each call, constant-time operations are performed.
● Therefore, the time complexity is O(n), linear with respect to the input size n.
Space Complexity:
● The space complexity is not constant due to recursive calls.
● Each recursive call adds a stack frame to the function call stack.
● In the worst case, the maximum depth of the recursion is n.
● Therefore, the space complexity is O(n), linear with respect to the input size n.
Step Operation Time Complexity
Variable Declaration int n; O(1) O(1)
Input Reading cin >> n; O(1) O(1)
Function Call sum_of_n(n); O(n) O(n)
Base Case if (n == 0) O(1) O(1)
Recursive Call return n + O(n) O(n)
sum_of_n(n - 1);
Result Output cout << "The sum O(1) O(1)
of first " << n
<< " ... ;
Total Complexity O(n) O(n)
BINARY SEARCH
Binary search works by repeatedly dividing the search interval in half. It compares the target
value with the middle element of the array and decides to continue searching in the left half or
the right half based on the comparison. This approach allows it to achieve a time complexity of
O(logn), where n is the number of elements in the array.
Example
Let's consider an array [2, 4, 6, 8, 10, 12, 14, 16] and we want to find the index
of 10.
Step Left Right Middle Comparison New Interval
1 0 7 3
arr[3] = 8 [10, 12, 14,
< 10 16]
2 4 7 5
arr[5] = [10, 12]
12 > 10
3 4 4 4
arr[4] = Found at
10 = 10 index 4
Binary Search Algorithm
1. Initialization:
○ Start with two pointers, low and high, set to the beginning and end of the array
respectively.
2. Iterative Search:
○ While low is less than or equal to high:
■ Calculate the middle index: mid = low + (high - low) / 2.
■ If the middle element is equal to the target value, return the middle index.
■ If the target value is less than the middle element, set high to mid - 1.
■ If the target value is greater than the middle element, set low to mid +
1.
3. Completion:
○ If the target value is not found, return -1.
Program of Binary Search
#include <iostream>
using namespace std;
// Binary search function
int binarySearch(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (arr[middle] == target) {
return middle; // Element found, return index
} else if (arr[middle] < target) {
left = middle + 1; // Target is in the right half
} else {
right = middle - 1; // Target is in the left half
} return -1; // Element not found
int main() {
int arr[] = {2, 4, 6, 8, 10, 12, 14, 16};
int size = sizeof(arr) / sizeof(arr[0]); // Calculate the size of array
int target = 10;
int index = binarySearch(arr, size, target);
if (index != -1) {
cout << "Element found at index: " << index << endl;
} else {
cout << "Element not found" << endl;
return 0;
Time Complexity and Space Complexity
● Time Complexity: O(logn) - Binary search halves the search space in each step, leading
to logarithmic time complexity.
● Space Complexity: O(1) - Binary search requires constant extra space, independent of the
input size, for storing variables like left, right, and middle.
