Please enable JavaScript.
Coggle requires JavaScript to display documents.
Competetive programming (Efficiency (O(f(n)) (O(1) - constant time. A…
Competetive programming
Efficiency
O(f(n))
O(1) - constant time. A typical constant type algorithm is a direct formula that calculates the answer
O(log n) - logarithmic. Often halves the input size in each step. log2 n is the number of times n must be divided by 2 to get 1.
-
-
O(n log n) often indicates that the algorithm sorts the input, or uses a special data structure.
O(n^2) a quadratic algorithm, often contains two nested loops, usually to find all the pairs
O(n^3) a cubic algorithm, often contains three nested loops, to find all the triplets.
-
-
O(f(n)) is an upper bound for the running time of the algorithm for sufficiently large inputs. There are constants c and n0 such that the algorithm performs at most cf(n) operations for all inputs where n >= n0. A
-
-
-
Sorting
Binary Search. Divide input in half, or the step size.
-
-
-
-