Data Structures - Asymptotic Analysis( Big O, Theta θ, Omega Ω Notation)

Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst case scenario of an algorithm.

Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to work in a constant time. Other than the "input" all other factors are considered constant.The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t depend on machine specific constants, and doesn’t require algorithms to be implemented and time taken by programs to be compared. Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis. 

Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, the running time of one operation is computed as f(n) and may be for another operation it is computed as g(n2). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small.

Usually, the time required by an algorithm falls under three types −

Best Case − Minimum time required for program execution.

Average Case − Average time required for program execution.

Worst Case − Maximum time required for program execution.

Asymptotic Notations

Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.

Ο Notation

Ω Notation

θ Notation

Big Oh Notation, Ο

The notation Ο(n) is the formal way to express the upper bound of an algorithm's running time. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete. The Big O notation defines an upper bound of an algorithm, it bounds a function only from above. For example, consider the case of Insertion Sort. It takes linear time in best case and quadratic time in worst case. We can safely say that the time complexity of Insertion sort is O(n^2). Note that O(n^2) also covers linear time.

If we use Θ notation to represent time complexity of Insertion sort, we have to use two statements for best and worst cases:

1. The worst case time complexity of Insertion Sort is Θ(n^2).

2. The best case time complexity of Insertion Sort is Θ(n).

Omega Notation, Ω

The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete. Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an asymptotic lower bound.Ω Notation can be useful when we have lower bound on time complexity of an algorithm.

Theta Notation, θ

The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm's running time.The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior.

A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants. For example, consider the following expression.

3n3 + 6n2 + 6000 = Θ(n3)

Dropping lower order terms is always fine because there will always be a n0 after which Θ(n3) has higher values than Θn2) irrespective of the constants involved.

Volatile vs Atomic in Java

Volatile and Atomic are two different concepts. Volatile ensures, that a certain, expected (memory) state is true across different threads, while Atomics ensure that operation on variables are performed atomically.

Take the following example of two threads in Java:

Thread A:

value = 1;
done = true;
Thread B:

if (done)
  System.out.println(value);
Starting with value = 0 and done = false the rule of threading tells us, that it is undefined whether or not Thread B will print value. Furthermore value is undefined at that point as well! To explain this you need to know a bit about Java memory management (which can be complex), in short: Threads may create local copies of variables, and the JVM can reorder code to optimize it, therefore there is no guarantee that the above code is run in exactly that order. Setting done to true and then setting value to 1 would be a possible outcome of the JIT.

volatile only ensures, that at the moment of access of such a variable, the new value will be immediately visible to all other threads and the order of execution ensures, that the code is at the state you would expect it to be. So in case of the code above, defining done as volatile will ensure that whenever Thread B checks the variable, it is either false, or true, and if it is true, then value has been set to 1 as well.

As a side-effect of volatile, the value of such a variable is set thread-wide atomically (at a very minor cost of execution speed). This is however only important on 32-bit systems that i.E. use long (64-bit) variables (or similar), in most other cases setting/reading a variable is atomic anyways. But there is an important difference between an atomic access and an atomic operation. Volatile only ensures that the access is atomically, while Atomics ensure that the operation is atomically.

Take the following example:

i = i + 1;
No matter how you define i, a different Thread reading the value just when the above line is executed might get i, or i + 1, because the operation is not atomically. If the other thread sets i to a different value, in worst case i could be set back to whatever it was before by thread A, because it was just in the middle of calculating i + 1 based on the old value, and then set i again to that old value + 1. Explanation:

Assume i = 0
Thread A reads i, calculates i+1, which is 1
Thread B sets i to 1000 and returns
Thread A now sets i to the result of the operation, which is i = 1
Atomics like AtomicInteger ensure, that such operations happen atomically. So the above issue cannot happen, i would either be 1000 or 1001 once both threads are finished.

Does making all fields Final makes the class Immutable in Java?

One of the common misconceptions among many Java Programmer is that a class with all final fields automatically becomes Immutable. This is not correct, you can easily break immutability of certain class if the final field it contains is a mutable one, as we'll see in this article. One of the most common examples of this is a java.util.Date. You have to be extra cautious to keep your class' immutability intact with mutable fields. When you return a reference to a mutable object, you are sharing ownership of that reference with whoever receives it. This can break invariant, such as immutability.

Another example of this kind of pattern which can break immutability is returning collection or array from the getters method .

So, even though, the field which is pointing to Date or Collection or array object is final, you can still break the immutability of the class by breaking Encapsulation by returning a reference to the original mutable object.


There are two ways to avoid this problem, first, don't provide getters to mutable objects if you can avoid it. If you must, then consider returning a copy or clone of the mutable object. If you are returning a collection, you could wrap it as an unmodifiable collection. Since we cannot make an array final or unmodifiable in Java

How to make code Thread-Safe in Java

How to make code Thread-Safe in Java

There are multiple ways to make this code thread safe in Java:

1) Use synchronized keyword in Java and lock the getCount() method so that only one thread can execute it at a time which removes possibility of coinciding or interleaving.

2) use Atomic Integer, which makes this ++ operation atomic and since atomic operations are thread-safe and saves cost of external synchronization.

3) Immutable objects are by default thread-safe because there state can not be modified once created. Since String is immutable in Java, its inherently thread-safe.

4) Read only or final variables in Java are also thread-safe in Java.

5) Locking is one way of achieving thread-safety in Java.

6) Static variables if not synchronized properly becomes major cause of thread-safety issues.

7) Example of thread-safe class in Java: Vector, Hashtable, ConcurrentHashMap, String etc.

8) Atomic operations in Java are thread-safe e.g. reading a 32 bit int from memory because its an atomic operation it can't interleave with other thread.

9) local variables are also thread-safe because each thread has there own copy and using local variables is good way to writing thread-safe code in Java.

10) In order to avoid thread-safety issue minimize sharing of objects between multiple thread.

11) Volatile keyword in Java can also be used to instruct thread not to cache variables and read from main memory and can also instruct JVM not to reorder or optimize code from threading perspective.

Top 10 Coding guidelines in Java

The top 10 are as follows

1) Do not expose methods that use reduced-security checks to untrusted code. Certain methods use a reduced-security check that checks only that the calling method is authorized rather than checking every method in the call stack. Any code that invokes these methods must guarantee that they cannot be invoked on behalf of untrusted code.

2)  Do not use the clone()method to copy untrusted method parameters. Inappropriate use of the clone() method can allow an attacker to exploit vulnerabilities by providing arguments that appear normal but subsequently return unexpected values. Such objects may consequently bypass validation and security checks.

3)  Document thread-safety and use annotations where applicable. The Java language annotation facility is useful for documenting design intent. Source code annotation is a mechanism for associating metadata with a program element and making it available to the compiler, analyzers, debuggers, or Java Virtual Machine (JVM) for examination. Several annotations are available for documenting thread-safety.

4) Be aware of numeric promotion behavior. Promotions in which the operands are converted from an int to a float or from a long to a double can cause a loss of precision.

5) Use a try-with-resources statement to safely handle closeable resources. Using the try-with-resources statement prevents problems that can arise when closing resources with an ordinary try-catch-finally block, such as failing to close a resource because an exception is thrown as a result of closing another resource, or masking an important exception when a resource is closed.

6)  Use the same type for the second and third operands in conditional expressions. The complexity of the rules that determine the result type of a conditional expression can result in unintended type conversions. Consequently, the second and third operands of each conditional expression should have identical types.

7) Avoid inadvertent wrapping of loop counters. Unless coded properly, a while or for loop may execute forever, or until the counter wraps around and reaches its final value.

8) Strive for logical completeness. Software vulnerabilities can result when a programmer fails to consider all possible data states.

9) Do not confuse abstract object equality with reference equality. Naïve programmers often confuse the intent of the == operation with that of the Object.equals() method. This confusion is frequently evident in the context of processing of String objects.

10) Understand how escape characters are interpreted when strings are loaded. Many classes allow inclusion of escape sequences in character and string literals. Correct use of escape sequences in string literals requires understanding how the escape sequences are interpreted by the Java compiler, as well as how they are interpreted by any subsequent processor.