DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment 3
Student Name: GRACY SINGH UID: 23BCS13667
Branch: BE CSE Section/Group: 630-A
Semester: 6 Date of Performance: 30/7/25
Subject Name: DAA Subject Code: 23CSH-301
1. Aim: Compute the time complexity to find frequency of elements in a given
array.
2. Objective: To find frequency of elements in a given array.
3. Algorithm:
STEP 1: Sort the Array: Arrange the array elements in ascending order.
STEP 2: Initialize Frequency Map: Create an empty map to store the
frequency of each element.
STEP 3: Count Frequencies: Traverse the sorted array, counting occurrences
of each element. Update the frequency map when a new element is encountered.
STEP 4: Add Last Element's Frequency: After the loop, add the frequency of
the last element to the map.
STEP 5: Print Frequencies: Iterate through the frequency map and print each
element with its corresponding frequency.
4. Implementation/Code:
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
cout<<"Frequencies in this sorted array: "<<endl;
int arr[] = {13, 22, 7, 9, 22, 13, 9, 99};
int size = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + size);
map<int, int> freqMap;
int count = 1;
for (int i = 1; i < size; i++) {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
if (arr[i] == arr[i - 1]) {
count++;
} else {
freqMap[arr[i - 1]] = count;
count = 1;
}
}
freqMap[arr[size - 1]] = count;
for (auto& pair : freqMap) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
5. Output:
6. Time Complexity: The time complexity of code is O(nlogn).
The space complexity of code is O(n).
7. Learning Outcome:
Understand how sorting an array helps in grouping similar elements together,
simplifying frequency counting.
Learn how to count occurrences of each element using a map or dictionary to
store these counts.
Gain skills in iterating through sorted data to calculate frequencies and update
counts efficiently.
Learn to present data clearly by iterating through a map and displaying results
in a readable format.
