C O M P L E X I T Y

Know Thy Complexities!

Hi there!  This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them.

Good

Fair

Poor

Searching

Algorithm	Data Structure	Time Complexity		Space Complexity
		Average	Worst	Worst
Depth First Search (DFS)	Graph of |V| vertices and |E| edges	-	O(|E| + |V|)	O(|V|)
Breadth First Search (BFS)	Graph of |V| vertices and |E| edges	-	O(|E| + |V|)	O(|V|)
Binary search	Sorted array of n elements	O(log(n))	O(log(n))	O(1)
Linear (Brute Force)	Array	O(n)	O(n)	O(1)
Shortest path by Dijkstra, using a Min-heap as priority queue	Graph with |V| vertices and |E| edges	O((|V| + |E|) log |V|)	O((|V| + |E|) log |V|)	O(|V|)
Shortest path by Dijkstra, using an unsorted array as priority queue	Graph with |V| vertices and |E| edges	O(|V|^2)	O(|V|^2)	O(|V|)
Shortest path by Bellman-Ford	Graph with |V| vertices and |E| edges	O(|V||E|)	O(|V||E|)	O(|V|)

Sorting

Algorithm	Data Structure	Time Complexity			Worst Case Auxiliary Space Complexity
		Best	Average	Worst	Worst
Quicksort	Array	O(n log(n))	O(n log(n))	O(n^2)	O(n)
Mergesort	Array	O(n log(n))	O(n log(n))	O(n log(n))	O(n)
Heapsort	Array	O(n log(n))	O(n log(n))	O(n log(n))	O(1)
Bubble Sort	Array	O(n)	O(n^2)	O(n^2)	O(1)
Insertion Sort	Array	O(n)	O(n^2)	O(n^2)	O(1)
Select Sort	Array	O(n^2)	O(n^2)	O(n^2)	O(1)
Bucket Sort	Array	O(n+k)	O(n+k)	O(n^2)	O(nk)
Radix Sort	Array	O(nk)	O(nk)	O(nk)	O(n+k)

Data Structures

Data Structure	Time Complexity								Space Complexity
	Average				Worst				Worst
	Indexing	Search	Insertion	Deletion	Indexing	Search	Insertion	Deletion
Basic Array	O(1)	O(n)	-	-	O(1)	O(n)	-	-	O(n)
Dynamic Array	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)	O(n)
Singly-Linked List	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Doubly-Linked List	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Skip List	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)	O(n)	O(n)	O(n)	O(n log(n))
Hash Table	-	O(1)	O(1)	O(1)	-	O(n)	O(n)	O(n)	O(n)
Binary Search Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)	O(n)	O(n)	O(n)	O(n)
Cartresian Tree	-	O(log(n))	O(log(n))	O(log(n))	-	O(n)	O(n)	O(n)	O(n)
B-Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
Red-Black Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
Splay Tree	-	O(log(n))	O(log(n))	O(log(n))	-	O(log(n))	O(log(n))	O(log(n))	O(n)
AVL Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)

Heaps

Heaps	Time Complexity
	Heapify	Find Max	Extract Max	Increase Key	Insert	Delete	Merge
Linked List (sorted)	-	O(1)	O(1)	O(n)	O(n)	O(1)	O(m+n)
Linked List (unsorted)	-	O(n)	O(n)	O(1)	O(1)	O(1)	O(1)
Binary Heap	O(n)	O(1)	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(m+n)
Binomial Heap	-	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))
Fibonacci Heap	-	O(1)	O(log(n))*	O(1)*	O(1)	O(log(n))*	O(1)

Graphs

Node / Edge Management	Storage	Add Vertex	Add Edge	Remove Vertex	Remove Edge	Query
Adjacency list	O(|V|+|E|)	O(1)	O(1)	O(|V| + |E|)	O(|E|)	O(|V|)
Incidence list	O(|V|+|E|)	O(1)	O(1)	O(|E|)	O(|E|)	O(|E|)
Adjacency matrix	O(|V|^2)	O(|V|^2)	O(1)	O(|V|^2)	O(1)	O(1)
Incidence matrix	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|E|)

Notation for asymptotic growth

letter	bound	growth
(theta) Θ	upper and lower, tight[1]	equal[2]
(big-oh) O	upper, tightness unknown	less than or equal[3]
(small-oh) o	upper, not tight	less than
(big omega) Ω	lower, tightness unknown	greater than or equal
(small omega) ω	lower, not tight	greater than

[1] Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight bound (it must be both the upper and lower bound). For example, an algorithm taking Omega(n log n) takes at least n log n time but has no upper limit. An algorithm taking Theta(n log n) is far preferential since it takes AT LEAST n log n (Omega n log n) and NO MORE THAN n log n (Big O n log n).SO

[2] f(x)=Θ(g(n)) means f (the running time of the algorithm) grows exactly like g when n (input size) gets larger. In other words, the growth rate of f(x) is asymptotically proportional to g(n).

[3] Same thing. Here the growth rate is no faster than g(n). big-oh is the most useful because represents the worst-case behavior.

In short, if algorithm is __ then its performance is __

algorithm	performance
o(n)	< n
O(n)	≤ n
Θ(n)	= n
Ω(n)	≥ n
ω(n)	> n

Garbage collector(s)

1. Garbage collector can be generational or single spaced with a parallel or a concurrent mark and a parallel sweep or a concurrent sweep.
2. Generational garbage collection – In this case the heap is divided into two sections: an old generation and a young generation (nursery). Initially objects are allocated in the nursery and when it is full, live objects are promoted to the old generation. For this operation the collector has to stop the Java threads.
3. Single-spaced garbage collection – All objects live in a single space on the heap, regardless of their age.
4. Concurrent mark and sweep algorithm – The concurrent garbage collection algorithm does its marking and sweeping concurrently with all other processing, i.e., the Java threads are not stopped during garbage collection.
5. allel garbage collection mark and sweep algorithm – The parallel garbage collection algorithm stops Java threads when the heap is full and uses all available CPUs to perform a mark and sweep of the heap. Typically a parallel collection has longer pause times than a concurrent collection, but maximizes the application throughput.

We can select a specific garbage collector by using -Xgc:<option>, with option being one of the following:

• singlecon – Single-space, concurrent garbage collection. This mode reduces application throughput but keeps pause times to a minimum.
• gencon – Generational, concurrent garbage collection. The gencon mode is better than the singlecon mode for applications that allocate lots of short-lived objects. This mode reduces application throughput but keeps pause times to a minimum.
• singlepar – Single-space, parallel garbage collection. This mode increases pause times when compared with the concurrent mode but maximizes throughput.
• genpar – Generational, parallel garbage collection. This mode is generally better than the singlepar mode for applications that allocate lots of short-lived objects. In this mode, a higher number of garbage collections are performed than in the singlepar mode, but the individual pause times are shorter, resulting in lower fragmentation in the old generation space.
• genconpar – Generational garbage collection. Sets the garbage collection mode to generational with a concurrent mark algorithm and a parallel sweep algorithm.
• genparcon – Generational garbage collection. Sets the garbage collection mode to generational with a parallel mark algorithm and a concurrent sweep algorithm.
• singleconpar – Single-space garbage collection. Sets the garbage collection mode to single-spaced with a concurrent mark algorithm and a parallel sweep algorithm.
• singleparcon – Single-space garbage collection. Sets the garbage collection mode to single-spaced with a parallel mark and a concurrent sweep algorithm.
• throughput – The garbage collector is optimized for application throughput. This means that the garbage collector works as effectively as possible, giving as much CPU resources to the Java threads as possible. This might, however, cause non-deterministic pauses when the garbage collector stops all Java threads for garbage collection.
• pausetime – The garbage collector is optimized for short pauses. This means that the garbage collection works concurrently with the Java application when necessary, in order to avoid pausing the Java threads. This inflicts a slight performance overhead to the application, as the concurrent garbage collector demands more system resources (CPU time and memory) than the parallel garbage collector that is used for optimal throughput. The target pause time is by default 200 milliseconds, which can be changed by using -XpauseTarget.
• deterministic – Optimizes the garbage collector for very short and deterministic pause times. The garbage collector tries to keep the garbage collection pauses below a given pause target. The performance depends on the application and the hardware. Running on slower hardware, with a different heap size or with a large amount of live data can break the deterministic behavior or cause performance degradation over time; faster hardware or a less amount of live data might allows us to set a lower pause target. The pause target for the deterministic mode is by default 30 milliseconds, which can be changed by using -XpauseTarget

Encrypt / decrypt messages using Cryptography Algorithm AES (Advance Encryption Algorithm)

What is AES ?
AES stands for Advance Encryption Algorithm. AES is a standard of private key or symmetric algorithm.

How To Use This Custom AES Encryption & Decryption with Oracle Service Bus 10g or 11g. ?
Extract the String from any Input Message, let say XML Message, you can easily do so by using XPath expression.
Pass this value to Java Callout Action in Oracle Service Bus Message Flow. For AES Encryption and decryption we are going to use Key and Initial Vector. This Key  and Initial vector can be stored in domain path so that it can be made configurable.

Below example shows how to create a Java Class for AES Encryption & Decryption which can be used with Oracle Service Bus 10g/11g to encrypt & decrypt messages. Method you want to call from Oracle Service Bus should be declared as public static. Only Public static methods are available to Oracle Service Bus using Java Callout. After Java Callout you can save the output of the call to any variable inside Service Bus.

Advantage: After transport level security it also necessary that once message is delivered to the destination, that Message's important fields need to be secured while getting processed in Destination. And Encrypting those field could be one of the solution and easy to implement if you have little understanding & knowledge about AES Encryption & Decryption Cryptography.

AES Support In Java Technology:
In java to support AES, Its has been provided as JCE in starting with Java2 SDK Standard edition (J2SE) v 1.4.0. Java Cryptography Extension (JCE) was integrated with  SDK and JRE and since then its not required to install JCE as a separate package.

AES supports combination of keys and block sizes. AES can support 128 , 192 and 256 block sizes.
128 block size - Secure
192 block size - More secure
256 block size - Most Secure

Following examples shows how to use AES Encryption and decryption. This program shows example of AES Cryptography implementation in Java. To implement & run this program you will require to have Jdk 1.4 or higher version.

---

import java.math.BigInteger;
import javax.crypto.Cipher;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.SecretKeySpec;
import sun.misc.BASE64Decoder;
import sun.misc.BASE64Encoder;

/* This class provides a sample example on how to use key and initial vector
 * to encrypt and decrypt String values  using AES Cryptography Algorithm
 */
public class AES4 {
    public static void main(String args[]){
            getAESEncryptedString("SampleStringTobeEncrypted","ddafXA1afcf6b1cb","a33dc00670g13ed7");
     }
/* This method takes string value and returns encrypted string back.
 * @param passwordAsString This is string argument which we want to encrypt , values could be some password
 * @param keyAsString This is Key , which we are using for encrypting the string.(Hex representation)
 * @param initialVectorAsString This is initialvector we are using for encrypting the string.
 * @return return value is Encrypted String
 */
     public static String getAESEncryptedString(String passwordAsString,String keyAsString, String initialVectorAsString) {
         try {
             byte[] key = new BigInteger(strToHex(keyAsString), 16).toByteArray();
             byte[] iv = new BigInteger(strToHex(initialVectorAsString), 16).toByteArray();
             //byte[] key = {0x64,0x64,0x31,0x62,0x58,0x41,0x31,0x61,0x66,0x36,0x66,0x36,0x39,0x31,0x63,0x62};
             // byte[] iv =  {0x61,0x32,0x32,0x65,0x63,0x37,0x30,0x36,0x30,0x30,0x67,0x31,0x33,0x65,0x64,0x38};
             System.out.println("key value in bytes : " + key);
             String text = passwordAsString;
             String encrypted = encrypt(text, iv, key);
             System.out.println("Pass  encrypted is " + encrypted);
             String decrypted = decrypt(encrypted, iv, key);
             System.out.println(encrypted + " decrypted is " + decrypted);
             return encrypted;
         } catch (Exception e) {
             e.printStackTrace();
         }
         return null;
     }
/* This method converts String value to its equivalent Hex Representation.
 * @param str This is string to be converted to its equivalent Hex representation.
 * @return return string in Hex Representation
 */
     public static String strToHex(String str) {
         char[] chars = str.toCharArray();
         StringBuffer hexStr = new StringBuffer();

        for (int i = 0; i < chars.length; i++){
                        hexStr.append(Integer.toHexString((int) chars[i]));
        }
         return strBuffer.toString();
     }

/* encrypt method encrypts the string provided using provide key and initial vector.
 * @param text String value to be encrypted
 * @param iv Initial Vector's byte Array value
 * @param key Key's byte Array Value
 * @return String This is encrypted String
 */
     public static String encrypt(String text, byte[] iv, byte[] key)throws Exception {
         Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
        SecretKeySpec keySpec = new SecretKeySpec(key, "AES");
         IvParameterSpec ivSpec = new IvParameterSpec(iv);
        cipher.init(Cipher.ENCRYPT_MODE, keySpec, ivSpec);
         byte[] results = cipher.doFinal(text.getBytes("UTF-8"));
         BASE64Encoder encoder = new BASE64Encoder();
         return encoder.encode(results);
     }
/* decrypt method decrypts the string using provide key and initial vector.
 * @param text String value to be decrypted
 * @param iv Initial Vector's byte Array value
 * @param key Key's byte Array Value
 * @return String This is decrypted String
 */
     public static String decrypt(String text, byte[] iv, byte[] key)throws Exception {
         Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
         SecretKeySpec keySpec = new SecretKeySpec(key, "AES");
         IvParameterSpec ivSpec = new IvParameterSpec(iv);
         cipher.init(Cipher.DECRYPT_MODE, keySpec, ivSpec);

         BASE64Decoder decoder = new BASE64Decoder();
         byte[] results = cipher.doFinal(decoder.decodeBuffer(text));
         return new String(results, "UTF-8");
    }
}