Time Complexity and Space Complexity:
Sometimes, there are more than one way to solve a problem. We need to learn how to compare the performance different algorithms and choose the best one to solve a particular problem. While analyzing an algorithm, we mostly consider time complexity and space complexity. Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. Similarly, Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.
Time and space complexity depends on lots of things like hardware, operating system, processors, etc. However, we don’t consider any of these factors while analyzing the algorithm. We will only consider the execution time of an algorithm.
O-Notation:
To denote asymptotic upper bound, we use O-notation. For a given function g(n), we denote by O(g(n)) (pronounced “big-oh of g of n”) the set of functions:
O(g(n))= { f(n) : there exist positive constants c and n0 such that 0≤f(n)≤c∗g(n) for all n≥n0 }
Ω-Notation:
To denote asymptotic lower bound, we use Ω-notation. For a given function g(n), we denote by Ω(g(n)) (pronounced “big-omega of g of n”) the set of functions:
Ω(g(n))= { f(n) : there exist positive constants c and n0 such that 0≤c∗g(n)≤f(n) for all n≥n0 }
Θ-notation:
To denote asymptotic tight bound, we use Θ-notation. For a given function g(n), we denote by Θ(g(n)) (pronounced “big-theta of g of n”) the set of functions:
Θ(g(n))= { f(n) : there exist positive constants c1,c2 and n0 such that 0≤c1∗g(n)≤f(n)≤c2∗g(n) for all n>n0 }


Searches In Arrays:
1) Linear Search in Java:
Linear search is used to search a key element from multiple elements. Linear search is less used today because it is slower than binary search and hashing.
Algorithm:
- Step 1: Traverse the array
- Step 2: Match the key element with array element
- Step 3: If key element is found, return the index position of the array element
- Step 4: If key element is not found, return -1

Example:
// Java code for linearly searching x in arr[]. If x
// is present then return its location, otherwise
// return -1
class LinearSearch{
public static int search(int arr[], int x) {
int n = arr.length;
for(int i = 0; i < n; i++) {
if(arr[i] == x)
return i;
}
return -1;
}
public static void main(String args[]) {
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int result = search(arr, x);
if(result == -1)
System.out.print(“Element is not present in array”);
else
System.out.print(“Element is present at index “ + result);
}
}
Element is present at index 3The time complexity of above algorithm is O(n).
Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster searching comparison to Linear search.
2) Binary Search:
Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].
A simple approach is to do linear search.The time complexity of above algorithm is O(n). Another approach to perform the same task is using Binary Search.
Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
Algorithm:
Input: Array and Target key
Output: Index
Pre-condition: Array is dorted
- Let p=0 and q=n-1
- Repeat step 2–5 while p≤q
- Let i=(p+q)/2
- if a[i]=key, return i
- if a[i]<x, let p=i+1; otherwise q=i-1
- return -i;

Example:
import java.util.Random;
import java.util.Scanner;
public class ArrayBinarySearch{
public static void sort(int []a){
int temp;
for(int i=0;i<a.length;i++){
for(int j=0;j<a.length-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
public static int binarySearch(int []a,int key){
int p=0;
int q=a.length-1;
int i=-1; //initially initializing with negative value
while(p<=q){
i=(p+q)/2;
if(a[i]==key){
return i;
}
if(a[i]<key){ //We will search from the right side
p=i+1; //Now p has the index 1 greater from middle index
}
else{
q=i-1; //To search from left q has index one less from middle index
}
}
return -i;
}
public static void main(String[]args){
int key; //element to search
Scanner sc = new Scanner(System.in);
Random rd = new Random();
int []arr=new int[100];
for(int i=0;i<arr.length;i++){
arr[i]=rd.nextInt(1000); //where 1000 is the range
}
//Printing the original array
System.out.println(“Unsorted Array”);
for(int i=0;i<arr.length;i++){
System.out.println(“arr[“+i+”]= “+arr[i]);
}
//It is necessary to sort the array for the binary search
ArrayBinarySearch.sort(arr);
//printing the sorted array
System.out.println(“Sorted Array”);
for(int i=0;i<arr.length;i++){
System.out.println(“arr[“+i+”]= “+arr[i]);
}
System.out.print(“Enter Element to search: “);
key=sc.nextInt();
int index=ArrayBinarySearch.binarySearch(arr, key);
if(index>=0){
System.out.println(“Element found, position is “+index);
}
else{
System.out.println(“Element not found”);
}
}
}