Big O Notation & Data Structures Flashcards
What is Big O Notation?
Big O Notation is a way to measure an algorithm’s efficiency.
What does it mean if an operation is O(log n)?
O(log n) means that as the input size grows, the number of operations grows very slowly.
Why do we use Big O notation to compare algorithms?
Big-O nation gives you a quick and easy way to communicate how efficient an algorithm is. This makes it easier to decide between different algorithms. This can be particularly helpful if you are using an algorithm from a library and do not necessarily know what the code looks like.
Explain the difference between O(1) vs O(n) space complexities.
O(1) denotes constant space use: the algorithm allocates the same number of pointers irrespective to the list size. In contrast, O(N) denotes linear space use: the algorithm space use grows together with respect to the input size.
Provide an example of an O(1) algorithm
if, for example, an algorithm takes the same time to process ten elements and 1 million items, then we say that it has a constant growth rate or O(1) .
What is the complexity of this code snippet?
for (int i = 0; i < n; i++) {
if (array[i] == numToFind) { return i; }
}
This function runs in O(n) time (or “linear time”), where n is the number of items in the array. If the array has 10 items, we have to print 10 times. If it has 1000 items, we have to print 1000 times.
What is complexity of push and pop for a Stack implemented using a LinkedList?
For all the standard stack operations (push, pop, isEmpty, size), the worst-case run-time complexity can be O(1).
When would you use a Hashtable over a Hashmap?
HashMap should be preferred over Hashtable for the non-threaded applications. In simple words , use HashMap in unsynchronized or single threaded applications . We should avoid using Hashtable, as the class is now obsolete in latest Jdk 1.8.
The only time one would use a Hashtable over a Hashmap is to store, retrieve, and delete data uniquely based on their unique key.
It is also useful when you don’t know exactly how many elements you’ll have, but there will be a good number fewer collisions on the hash function than your total number of elements.
When would you use a List over a Set?
You would use a List over a Set when the order is important.
The main difference between List and Set is that List allows duplicates while Set doesn’t allow duplicates. List is an ordered collection it maintains the insertion order, which means upon displaying the list content it will display the elements in the same order in which they got inserted into the list.
When would you use a LinkedList over a ArrayList?
LinkedList should be used where modifications to a collection are frequent like addition/deletion operations.
