O(n) Linear Time:
Imagine you are at a big Indian family gathering, and you’re trying to avoid that one aunty who always asks, “Beta, when are you getting married?” To spot her before she spots you, you start scanning the room, looking at each relative one by one. If she’s hidden right at the back, chatting with some distant cousins, you’d have to spot every other relative before you find her. It’s like playing a real-life game of “Hide and Seek”, but instead of seeking friends, you’re dodging matrimonial interrogations. That’s the linear drama of large family gatherings.
Now, if it’s just a small family dinner, evading Aunty’s question is as easy as sneaking an extra ladoo when no one’s looking. But imagine if it’s a massive Diwali party! You might end up having to dodge questions from multiple aunties and uncles, all asking about your job, your salary, and when you’ll buy a house!
Other way to understand this is, Imagine you have a list of numbers, and you want to check if a particular number exists in that list. The most straightforward way would be to start from the beginning of the list and check each number one by one.
In the worst-case scenario, you might have to check all the numbers in the list. The time it takes to complete this task grows proportionally with the size of the list. This is a linear relationship.
For smaller datasets, a linear time algorithm might be perfectly adequate. However, as datasets grow, we might look for more efficient algorithms (like logarithmic or constant time algorithms) to handle the data more effectively.
int sum(int arr[], int size) {
int total = 0;
for (int i = 0; i < size; i++) {
total += arr[i];
}
return total;
}
In this function, the loop runs size times. The time it takes to complete grows linearly with the size of the array. The loop iterates over each element of the array once, adding its value to the total. This is a O(n) scenario.
int countOccurrences(int arr[], int size, int target) {
int count = 0;
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
count++;
}
}
return count;
}
The loop iterates over the array, checking if each element matches the target. If it does, the count is incremented. The loop runs size times, making the function’s complexity O(n).
void copyArray(int source[], int destination[], int size) {
for (int i = 0; i < size; i++) {
destination[i] = source[i];
}
}
Here, the loop iterates over each element of the source array and copies it to the destination array. The loop runs a total of size times, making the function’s complexity O(n). A single loop runs based on the size of the input (size). No nested loops or recursive calls are present. The loop directly operates on each element of the array.
int countEven(int arr[], int size) {
int count = 0;
for (int i = 0; i < size; i++) {
if (arr[i] % 2 == 0) {
count++;
}
}
return count;
}
This function counts the number of even integers in the array. The loop runs through each element once, checking its parity. Since the loop runs size times, the time complexity is O(n).
float findAverage(int arr[], int size) {
int sum = 0;
for (int i = 0; i < size; i++) {
sum += arr[i];
}
return (float)sum / size;
}
The function calculates the average of the elements in the array. The loop iterates over the entire array once, summing up the values. The loop runs size times, giving us a time complexity of O(n).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
An Article by: Yashwanth Naidu Tikkisetty
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Cosmic Writer 