If you want examples of Algorithms/Group of Statements with Time complexity as given in the question, here is a small list – O(1) time Accessing Array Index (int a = ARR[5];) Inserting a node in Linked List Pushing and Poping on Stack Insertion and Removal from Queue Finding out the parent or left/right child of … Read more
According to a recent episode of Radiolab (about “Falling”), a cat reaches terminal velocity by the 9th floor. After that, it relaxes and is less likely to be hurt. There are completely uninjured cats after a fall from above the 30th. The riskiest floors are 5th to 9th.
Ok, so I’m tired as it’s 3AM here, but I have a first try inplace with exactly 2 passes on each number in the matrix, so in O(NxN) and it is linear in the size of the matrix. I use 1rst column and first row as markers to know where are rows/cols with only 1’s. … Read more
Backtracking is a more general purpose algorithm. Depth-First search is a specific form of backtracking related to searching tree structures. From Wikipedia: One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking. It uses backtracking as part of its … Read more
Here a more mathematical way of seeing it, though not really complicated. IMO much clearer as informal ones: The question is, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be … Read more
The fastest algorithm for general prime testing is AKS. The Wikipedia article describes it at lengths and links to the original paper. If you want to find big numbers, look into primes that have special forms like Mersenne primes. The algorithm I usually implement (easy to understand and code) is as follows (in Python): def … Read more
What’s the main reason for choosing Red black trees instead of AVL trees? Both red-black trees and AVL trees are the most commonly used balanced binary search trees and they support insertion, deletion and look-up in guaranteed O(logN) time. However, there are following points of comparison between the two: AVL trees are more rigidly balanced … Read more
Compute unit vectors from the angles and take the angle of their average.
These are simply ideas I’ve had thinking about the problem, never tried it but I like thinking about problems like this! Before you begin Consider normalising the pictures, if one is a higher resolution than the other, consider the option that one of them is a compressed version of the other, therefore scaling the resolution … Read more
Advantages of tries: The basics: Predictable O(k) lookup time where k is the size of the key Lookup can take less than k time if it’s not there Supports ordered traversal No need for a hash function Deletion is straightforward New operations: You can quickly look up prefixes of keys, enumerate all entries with a … Read more