Tag Archives: Time and Space Complexity

Data Structure and Algorithms Complexity (Big-O)


Big-O notation is a mathematical representation used to describe the complexity of a data structure and algorithm. There are two types of Complexity :

  1. Time Complexity: Its measure based on steps need to follow for an algorithm.
  2. Space Complexity: It measures the space required to perform an algorithm and data structure.

Data Structure and Algorithm Decision

Data structure and algorithm decisions are based on the complexity of size and operations need to perform on data. Some algorithms perform better on a small set of data while others perform better for big data sets for certain operations.

These days Space Complexity is not big concerns but the main performance of an algorithm measures based on time complexity. We can make the decision to choose an algorithm based on below performance criteria with respect to Complexity.

Complexity Performance
O(1) Excellent
O(log(n)) Good
O(n) Fair
O(n log(n)) Bad
O(n^2) Horrible
O(2^n) Horrible
O(n!) Horrible

This post almost covers data structure and algorithms space and time Big-O complexities. Here you can also see time complexities for types of operations like access, search, insertion, and deletion.

See also: 

Data Structure Space and Time Complexity

Data Structure Time Complexity Space Complexity
Average Worst
Access Search Insertion Deletion
Array Θ(1) Θ(n) Θ(n) Θ(n) O(n)
Stack Θ(n) Θ(n) Θ(1) Θ(1) O(n)
Queue Θ(n) Θ(n) Θ(1) Θ(1) O(n)
Singly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n)
Doubly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n)
Skip List Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n log(n))
Hash Table N/A Θ(1) Θ(1) Θ(1) O(n)
Binary Search Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
Cartesian Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
B-Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
Red-Black Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
Splay Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
AVL Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
KD Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)

Sorting Algorithms Space and Time Complexity

Algorithm Time Complexity Space Complexity
Best Average Worst Worst
Quick Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n))
Merge Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)
Tim Sort Ω(n) Θ(n log(n)) O(n log(n)) O(n)
Heap Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1)
Bubble Sort Ω(n) Θ(n^2) O(n^2) O(1)
Insertion Sort Ω(n) Θ(n^2) O(n^2) O(1)
Selection Sort Ω(n^2) Θ(n^2) O(n^2) O(1)
Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n)
Shell Sort Ω(n log(n)) Θ(n(log(n))^2) O(n(log(n))^2) O(1)
Bucket Sort Ω(n+k) Θ(n+k) O(n^2) O(n)
Radix Sort Ω(nk) Θ(nk) O(nk) O(n+k)
Counting Sort Ω(n+k) Θ(n+k) O(n+k) O(k)
Cube Sort Ω(n) Θ(n log(n)) O(n log(n)) O(n)

 

Advertisements

Binary Search Java Program


Binary search, also known as half-interval search,binary chop or logarithmic search.

How it Works?

Binary search works on sorted arrays values. Binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than or greater
than the middle element, the search continues in the lower or upper half of the array, respectively, eliminating the other half from consideration.If the search ends with the remaining half being empty, the target is not in the array.

Time and Space Complexity?

Binary search runs in at worst logarithmic time, making O(log n) comparisons and takes constant (O(1)) space.

where n is the number of elements in the array, the O is Big O notation, and log is the logarithm.

Java API  for Binary Search

Java Arrays class also provide api’s for Binary Search. You can use as below

import java.util.Arrays;

public class BinarySearchByJavaAPI {

	public static void main(String[] args) {
		char characters[] = { 'l', 'm', 'n', 'p', 'q<span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>' };

	    System.out.println(Arrays.binarySearch(characters, 'a'));
	    System.out.println(Arrays.binarySearch(characters, 'p'));

	}

}

Java Program for Binary Search

import java.util.Scanner;

class BinarySearch
{
  public static void main(String args[])
  {
    int c, first, last, middle, n, search, array[];

    Scanner in = new Scanner(System.in);
    System.out.println("Enter number of elements");
    n = in.nextInt();
    array = new int[n];

    System.out.println("Enter " + n + " sorted integers");

    for (c = 0; c < n; c++)
      array[c] = in.nextInt();

    System.out.println("Enter value to find");
    search = in.nextInt();

    first  = 0;
    last   = n - 1;
    middle = (first + last)/2;

    while( first <= last )
    {
      if ( array[middle] < search )                 first = middle + 1;                else if ( array[middle] == search )     {                System.out.println(search + " found at location " + (middle + 1) + ".");                break;        }        else                last = middle - 1;           middle = (first + last)/2;     }     if ( first ><span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span> last )
      System.out.println(search + " is not present in the list.\n");
  }
}

More Info

For more Algorithms and Java Programing Test questions and sample code follow below links