Tag Archives: List

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)

 

Elasticsearch REST JAVA Client to get Index Details List


Below is example to get Index Detail in Java Array by using Elasticsearch REST Java client. Here client will call endpoint  “/_cat/indices?format=json” to retrieve all detail of index list. It is same as we use GET by CURL

GET http://elasticsearchHost:9200/_cat/indices?format=json
 

Pre-requisite

  • Minimum requirement for Java 7 version required.
  • Add below dependency for Elasticsearch REST and JSON Mapping in your pom.xml or add in your class path.

Dependency

<!--Elasticsearch REST jar-->
<dependency>
			<groupId>org.elasticsearch.client</groupId>
			<artifactId>rest</artifactId>
			<version>5.1.2</version>
</dependency>
<!--Jackson jar for mapping json to Java -->
<dependency>
			<groupId>com.fasterxml.jackson.core</groupId>
			<artifactId>jackson-databind</artifactId>
			<version>2.8.5</version>
</dependency>

Sample Code

import java.io.IOException;
import java.util.Collections;

import org.apache.http.HttpEntity;
import org.apache.http.HttpHost;
import org.apache.http.auth.AuthScope;
import org.apache.http.auth.UsernamePasswordCredentials;
import org.apache.http.client.CredentialsProvider;
import org.apache.http.impl.client.BasicCredentialsProvider;
import org.apache.http.impl.nio.client.HttpAsyncClientBuilder;
import org.elasticsearch.client.Response;
import org.elasticsearch.client.RestClient;
import org.elasticsearch.client.RestClientBuilder;

import com.fasterxml.jackson.databind.ObjectMapper;

public class ElasticsearchRESTIndexClient {

	public static void main(String[] args) {
		IndexInfo []indexArr = null;
		RestClient client = null;
		try {
			client = openConnection();
			if (client != null) {
				// performRequest GET method will retrieve all index detail list
				// information from elastic server
				Response response = client.performRequest("GET", "/_cat/indices?format=json",
						Collections.singletonMap("pretty", "true"));
				// GetEntity api will return content of response in form of json
				// in Http Entity
				HttpEntity entity = response.getEntity();
				ObjectMapper jacksonObjectMapper = new ObjectMapper();
				// Map json response to Java object in IndexInfo Array
				// Cluster Info
				indexArr = jacksonObjectMapper.readValue(entity.getContent(), IndexInfo[].class);
				for(IndexInfo indexInfo:indexArr)
				{
				System.out.println(indexInfo);
			    }
			}

		} catch (Exception ex) {
			System.out.println("Exception found while getting cluster detail");
			ex.printStackTrace();
		} finally {
			closeConnnection(client);
		}

	}

	// Get Rest client connection
	private static RestClient openConnection() {
		RestClient client = null;
		try {
			final CredentialsProvider credentialsProvider = new BasicCredentialsProvider();
			credentialsProvider.setCredentials(AuthScope.ANY, new UsernamePasswordCredentials("userid", "password"));
			client = RestClient.builder(new HttpHost("elasticHost", Integer.parseInt("9200")))
					.setHttpClientConfigCallback(new RestClientBuilder.HttpClientConfigCallback() {
						// Customize connection as per requirement
						public HttpAsyncClientBuilder customizeHttpClient(HttpAsyncClientBuilder httpClientBuilder) {
							return httpClientBuilder
									// Credentials
									.setDefaultCredentialsProvider(credentialsProvider)
									// Proxy
									.setProxy(new HttpHost("proxyServer", 8080));

						}
					}).setMaxRetryTimeoutMillis(60000).build();

		} catch (Exception ex) {
			ex.printStackTrace();
		}
		return client;
	}

	// Close Open connection
	private static void closeConnnection(RestClient client) {
		if (client != null) {
			try {
				client.close();
			} catch (IOException ex) {
				ex.printStackTrace();
			}
		}
	}

}

Index Info Object where JSON index detail will map

import com.fasterxml.jackson.annotation.JsonIgnoreProperties;
import com.fasterxml.jackson.annotation.JsonProperty;

@JsonIgnoreProperties(ignoreUnknown = true)
public class IndexInfo {
@JsonProperty(value = "health")
private String health;
@JsonProperty(value = "index")
private String indexName;
@JsonProperty(value = "status")
private String status;
@JsonProperty(value = "pri")
private int shards;
@JsonProperty(value = "rep")
private int replica;
@JsonProperty(value = "pri.store.size")
private String dataSize;
@JsonProperty(value = "store.size")
private String totalDataSize;
@JsonProperty(value = "docs.count")
private String documentCount;

@Override
public String toString()
{
	StringBuffer str=new StringBuffer(60);
	str.append("{\n");
	str.append("    \"").append("indexName").append("\":\"").append(indexName).append("\",\n");
	str.append("    \"").append("health").append("\":\"").append(health).append("\",\n");
	str.append("    \"").append("status").append("\":\"").append(status).append("\",\n");
	str.append("    \"").append("shards").append("\":\"").append(shards).append("\",\n");
	str.append("    \"").append("replica").append("\":\"").append(replica).append("\",\n");
	str.append("    \"").append("dataSize").append("\":\"").append(dataSize).append("\",\n");
	str.append("    \"").append("totalDataSize").append("\":\"").append(totalDataSize).append("\",\n");
	str.append("    \"").append("documentCount").append("\":\"").append(documentCount).append("\"\n");
	str.append("    \"");
	return str.toString();
}
public String getIndexName() {
	return indexName;
}
public void setIndexName(String indexName) {
	this.indexName = indexName;
}
public int getShards() {
	return shards;
}
public void setShards(int shards) {
	this.shards = shards;
}
public int getReplica() {
	return replica;
}
public void setReplica(int replica) {
	this.replica = replica;
}
public String getDataSize() {
	return dataSize;
}
public void setDataSize(String dataSize) {
	this.dataSize = dataSize;
}
public String getTotalDataSize() {
	return totalDataSize;
}
public void setTotalDataSize(String totalDataSize) {
	this.totalDataSize = totalDataSize;
}
public String getDocumentCount() {
	return documentCount;
}
public void setDocumentCount(String documentCount) {
	this.documentCount = documentCount;
}
public String getStatus() {
	return status;
}
public void setStatus(String status) {
	this.status = status;
}
public String getHealth() {
	return health;
}
public void setHealth(String health) {
	this.health = health;
}
}

Read More on Elasticsearch REST

Integration

Integrate Filebeat, Kafka, Logstash, Elasticsearch and Kibana