Introduction

Computers can only do a limited number of operations in a given time, usually about a billion operations per second. Here, by an individual operation, we mean addition, multiplication, assigning a value to a variable, etc. Hence, if we want our algorithm to finish executing in a second or so, then we need to make sure that the total number of operations we are asking it to do is less than 1 billion.

Estimating the exact run-time of an algorithm without implementing and executing it is very tough since it depends on so many factors - including the programming language being used, the compiler, the hardware of the computer itself, and more. Instead, what we'd like to do most of the time, is to estimate the run-time approximately.

Rate of growth

In algorithms, we focus on estimating the execution ...

Recursion is a fundamental technique used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition.

In computer science, a common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances. A contrary approach is Dynamic Programming. This approach serves as a bottom-up approach, where problems are solved by solving larger and larger instances, until the desired size is reached.

Mathematical Induction

It's recommended that you learn mathematical inducti...

Motivation: Given an array of N numbers, you need to support two operations. Operation 1: find-min(i, j) = return the minimum value in array[i ... j]. Operation 2: update(i, v) = update the value at array[i] to v. Solve the problem for N <= 10^6, number of operations <= 10^6.

To solve the above problem, both the operations need to run in O(log N) time, but using an naive array gives O(N) run-time for operation 1 (and O(1) run-time for operation 2). So how do you solve the problem? Read on. :)

Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.

I found this tutorial helpful for people learning Sqrt-Decomposition - http://acm.math.spbu.ru/~sk1/mm/lections/mipt2016-sqrt/mipt-2016-burunduk1-sqrt.en.pdf

This tutorial contains tutorial on -

1. Sqrt-Decomposition on Trees (Heavy-Light)
2. Sqrt-Decomposition on Strings
3. Sqrt-Decomposition on Arrays
4. Sqrt-Decomposition on Arrays (Split and Rebuild)
5. Query-Buffering (Sqrt-Decomposition on Queries)

If anyone have any problem understanding something, lets discuss in reply :)

Visualization:

Algorithm:

1. Find the point with the lowest y-coordinate, break ties by choosing lowest x-coordinate. Call this point P. Add P to the convex hull.
2. Sort the remaining points in increasing or...