DEV Community: Binayak Jha

Linear Search: A Guide To DSA (2)

Binayak Jha — Thu, 01 Jun 2023 02:21:03 +0000

If you want to learn about Big O : Click Here

Linear Search:

Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.

Time Complexity: O(n) where n is the number of elements in the array, because the worst case scenario is that the element is not present in the array and we have to traverse the whole array.

Image of Linear Search Searching an Array:

Algorithm:

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

Example:

A = [2, 4, 0, 1, 9]
x = 1
n = 5

Solving the above example:

Step 1: i = 1
Step 2: 1 <= 5
Step 3: A[1] = 4 != 1
Step 4: i = 2
Step 5: 2 <= 5
Step 3: A[2] = 0 != 1
Step 4: i = 3
Step 5: 3 <= 5
Step 3: A[3] = 1 = 1
Step 6: Print Element 1 Found at index 3

Pseudocode:

procedure linear_search (list, value)

   for each item in the list
      if match item == value
         return the item's location
      end if
   end for

end procedure

Implementation:

C:

#include <stdio.h>
// Search an element in an array using linear search
void search(int arr[], int n, int x){
    int i;
    for(i=0; i<n; i++){
        if(arr[i] == x){
            printf("Element found at index %d", i+1);
            return;
        }
    }
    printf("Element not found");
}
// Main function
int main(){

    int arr[] = {10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 35;
    search(arr, n, x);
    return 0;
}

Java:

public class LinearSearchExample
{  
 public static int linearSearch(int[] arr, int key)
 {  
  for(int i=0;i<arr.length;i++)
  {  
   if(arr[i] == key)
   {  
     return i;  
   }  
  }  
  return -1;  
 }

 public static void main(String a[])
 {  
  int[] a1= {10,20,30,50,70,90};  
  int key = 50;  
  System.out.println(key+" is found at index: "+linearSearch(a1, key));  
 }  
}

Python:

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

arr = [2, 0, 1, 9]
x = 1

print("Element found at index " + str(linear_search(arr, x)))

C++:

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int x)
{
    for (int i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}

int main(void)
{
    int arr[] = { 2, 0, 1, 9 };
    int x = 1;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = linearSearch(arr, n, x);
    (result == -1)
        ? cout << "Element is not present in array"
        : cout << "Element is present at index " << result;
    return 0;
}

Follow me in Github For More: Click Here

Big O: A Beginner's Guide:

Binayak Jha — Tue, 14 Mar 2023 05:21:03 +0000

What is Big O?

Big O is a way to measure the efficiency of an algorithm. It is a way to describe the performance or complexity of an algorithm. It is a way to compare the efficiency of different algorithms.

In Simple terms, Big O is a way to measure how fast an algorithm is or As your input grows, how fast does the runtime of your algorithm grow.

The Big O notation is expressed using a mathematical formula that uses the letter "O" and a function of "n," which represents the input size.

The notation represents the rate of growth of an algorithm's runtime in terms of the input size.

How To Calculate Big O?

The Simplest trick to know the Big O of a function is to look for the loops in the function.

1) If there is a loop, then the Big O is O(n).

2) If there are two loops, then the Big O is O(n^2).

3) If there are three loops, then the Big O is O(n^3).

And so on. (n is the number of items in the loop)

For example, consider the following functions in C, Python and Java.

Example

1) C :



int sum(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += i;
    }
    return total;
}

2) Python :



def sum(n):
    total = 0
    for i in range(n):
        total += i
    return total

3) Java :



public int sum(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += i;
    }
    return total;
}

This code has a loop that iterates n times, so the Big O notation for this code is O(n).

Some Common Big O's Notations:

1) O(1) : Constant Time - No Loops

Examples of O(1):



// C Code
int print_first_element(int[] lst) {
    printf("%d", lst[0]);
}



# Python Code
def print_first_element(lst):
    print(lst[0])



// Java Code
public void print_first_element(int[] lst) {
    System.out.println(lst[0]);
}

2) O(n) : Linear Time - 1 Loop

Examples of O(n):



// C Code
int sum(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += i;
    }
    return total;
}



# Python Code
def sum(n):
    total = 0
    for i in range(n):
        total += i
    return total



// Java Code
public int sum(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += i;
    }
    return total;
}

3) O(n^2) : Quadratic Time - 2 Loops

Examples of O(n^2):



// C Code
int sum_of_pairs(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            total += i + j;
        }
    }
    return total;
}



# Python Code
def sum_of_pairs(n):
    total = 0
    for i in range(n):
        for j in range(n):
            total += i + j
    return total



// Java Code
public int sum_of_pairs(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            total += i + j;
        }
    }
    return total;
}

4) O(log n) : Logarithmic Time - Usually searching algorithms have log n if they are sorted (Binary Search)

Examples of O(log n):



// C Code
int binary_search(int[] lst, int target) {
    int low = 0;
    int high = lst.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        int guess = lst[mid];
        if (guess == target) {
            return mid;
        }
        if (guess > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}



# Python Code
def binary_search(lst, target):
    low = 0
    high = len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = lst[mid]
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
    return -1



// Java Code
public int binary_search(int[] lst, int target) {
    int low = 0;
    int high = lst.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        int guess = lst[mid];
        if (guess == target) {
            return mid;
        }
        if (guess > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

5) O(n log n) : Log Linear Time - Usually sorting operations

Examples of O(n log n):



// C Code
void merge_sort(int[] lst) {
    if (lst.length < 2) {
        return;
    }
    int mid = lst.length / 2;
    int[] left = new int[mid];
    int[] right = new int[lst.length - mid];
    for (int i = 0; i < mid; i++) {
        left[i] = lst[i];
    }
    for (int i = mid; i < lst.length; i++) {
        right[i - mid] = lst[i];
    }
    merge_sort(left);
    merge_sort(right);
    merge(left, right, lst);
}



# Python Code
def merge_sort(lst):
    if len(lst) < 2:
        return
    mid = len(lst) // 2
    left = lst[:mid]
    right = lst[mid:]
    merge_sort(left)
    merge_sort(right)
    merge(left, right, lst)



// Java Code
public void merge_sort(int[] lst) {
    if (lst.length < 2) {
        return;
    }
    int mid = lst.length / 2;
    int[] left = new int[mid];
    int[] right = new int[lst.length - mid];
    for (int i = 0; i < mid; i++) {
        left[i] = lst[i];
    }
    for (int i = mid; i < lst.length; i++) {
        right[i - mid] = lst[i];
    }
    merge_sort(left);
    merge_sort(right);
    merge(left, right, lst);
}

6) O(2^n) : Exponential Time - Usually recursive algorithms that solves a problem of size N

Examples of O(2^n):



// C Code
int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}



# Python Code
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)



// Java Code
public int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

7) O(n!) : Factorial Time - Usually recursive algorithms that solves a problem of size N

Examples of O(n!):



// C Code
int permutation(int[] lst, int k) {
    if (k == 1) {
        return 1;
    } else {
        return k * permutation(lst, k - 1);
    }
}



# Python Code
def permutation(lst, k):
    if k == 1:
        return 1
    else:
        return k * permutation(lst, k - 1)



// Java Code
public int permutation(int[] lst, int k) {
    if (k == 1) {
        return 1;
    } else {
        return k * permutation(lst, k - 1);
    }
}

Big O Graph:

You can see in the graph that the time complexity of the algorithm increases as the input size increases except for O(1) and O(log n) which are constant and logarithmic time complexity respectively.

The Big O Cheat Sheet: (Time Complexity) :

Note: The Big O Cheat Sheet is a summary of the most common time complexities of algorithms. It is not a complete list of all the time complexities of all the algorithms.

Big O of Common Data Structures: (Access, Search, Insertion, Deletion) :

Advanced Cheat Sheet

Calculating Time Complexity:

Note: The following are the steps to calculate the time complexity of an algorithm.

1) Dropping the Constants: Drop the constants in the time complexity. For example, O(2n) is the same as O(n).

2) Dropping the Non Dominants: Drop the non dominants in the time complexity. For example, O(n + n^2) is the same as O(n^2).

For example, the time complexity of the following algorithm is O(n^2):



// C Code
int sum = 0; // O(1)
for (int i = 0; i < n; i++) { // O(n)
    for (int j = 0; j < n; j++) { // O(n)
        sum += 1; // O(1)
    }
}



# Python Code
sum = 0 # O(1)
for i in range(n): # O(n)
    for j in range(n): # O(n)
        sum += 1 # O(1)



// Java Code
int sum = 0; // O(1)
for (int i = 0; i < n; i++) { // O(n)
    for (int j = 0; j < n; j++) { // O(n)
        sum += 1; // O(1)
    }
}

Calculating Time Complexity: O(1) + O(n) + O(n) + O(1) = O(2n) = O(n)

Conclusion

In this article, we have learned about the Big O Notation and how to calculate the time complexity of an algorithm. We have also learned about the Big O Cheat Sheet and the Big O of common data structures.

My Github: https://github.com/BinayakJha

Promoting Equality in the Tech Industry

Binayak Jha — Thu, 09 Mar 2023 02:08:04 +0000

The tech industry has been under scrutiny for its lack of diversity and inclusivity. Women, people of color, and other underrepresented groups have struggled to find equal footing in this industry, and it is important to recognize and address these challenges. In order to create a more equitable and inclusive tech industry, individuals must pledge to embrace equality in tech by taking proactive steps to support and uplift underrepresented groups.

How Do I Pledge To Embrace Equality In Tech?

I pledge to embrace equality in tech by first recognizing the barriers that exist and actively working to break them down. This involves challenging biases, stereotypes, and microaggressions that are pervasive in tech culture. By being mindful of my own language and behavior, and holding others accountable, I can help create a more welcoming and inclusive environment for everyone.

My Validating Experience:

One validating experience I had in the workplace was when I witnessed a female colleague receive a promotion that she deserved. She had worked tirelessly for the company, and her hard work and dedication paid off. Seeing her succeed and be recognized for her accomplishments was a reminder that progress towards equality in tech is possible. It is important to continue to advocate for and uplift women and other underrepresented groups in order to make the tech industry more equitable.

Biggest Obstacles:

One of the biggest obstacles to gender equality in the tech industry is the lack of representation in leadership positions. Women are often excluded from decision-making processes, which can perpetuate systemic biases and prevent progress towards greater equality. In order to address this issue, companies must actively seek out and hire diverse candidates, promote from within, and provide opportunities for leadership development and mentorship.

Diversity and inclusion initiatives have positively impacted my workplace by creating a more welcoming and inclusive environment for everyone. By valuing diversity and promoting inclusivity, employees are able to bring their whole selves to work and feel valued for their unique perspectives and experiences. This leads to increased collaboration, creativity, and productivity, as employees feel empowered to contribute to the company in meaningful ways.

Conclusion

I will commit to educating myself about the experiences of underrepresented groups in the tech industry, and advocating for their inclusion and advancement. This includes listening to and amplifying their voices, as well as seeking out resources and training to better understand the issues they face. By educating myself, I can be a more effective ally and advocate for equality in tech.