طراحی الگوریتمAlgorithms

Insertion sort is adaptive: it runs in Θ(n) on nearly-sorted input where merge/quicksort still pay Θ(nlog n) .

Floyd-Warshall is the dynamic-programming algorithm that finds shortest paths between every pair of vertices in Θ(n^3) .

Adding terms of lower-or-equal order keeps Theta; the largest term dominates, and identities can break when f is not assumed to grow.

Backtracking suits feasibility/constraint-satisfaction searches; Branch and Bound adds a cost bound for optimization.

On adjacency lists, BFS touches every undirected edge twice (once per endpoint), giving total work Θ(V+E) .

Dijkstra is correct iff all edge weights are non-negative; cycles (even directed) are irrelevant.

Dijkstra is correct only when all edge weights are non-negative; 'no negative cycle' is not enough.

Huffman greedily merges the smallest weights into an optimal prefix-free tree; the same rule gives k-ary (e.g. ternary) Huffman and optimal-merge patterns whose cost is the weighted path length.

Merging k sorted lists with n total elements costs Θ(nlog k) , which is O(n) only when k is constant.

Kruskal sorts edges by weight and accepts an edge only if its endpoints lie in different components; otherwise it would close a cycle and is rejected.

When the per-call work f(n) outgrows the watershed n^(log_b a), the recurrence is dominated by the top level and T(n)=Theta(f(n)).

Picking the exact median as pivot gives a perfectly balanced split, yielding T(n)=2T(n/2)+f(n)+Θ(n)=O((n+f(n))log n) .

Greedily build a cheapest set of edges that connects all vertices with no cycle, using exactly n-1 edges.

An algorithm cannot run faster than the size of the output it must produce, so enumerating exponentially many objects takes exponential time.

Each element of an n-set sits in exactly 2^(n-1) subsets, so the total of all subset-sums is 2^(n-1) times the element sum.

When the argument shrinks by a constant (n-1) instead of a factor, unroll the recurrence; a branching factor a>1 gives exponential growth Θ(a^n) .

A worst-case upper bound ("runs in at most ...") limits the slowest run but says nothing about average case or behavior on a specific input.

For an NP-hard optimization problem, a polynomial-time rho-approximation guarantees a solution within a factor rho of the optimum; the ratio is a monotone worst-case bound (factor c gives every c' >= c for free) and is defined only for optimization, never for decision, problems.

DP applies when an optimal solution is built from optimal solutions of overlapping subproblems; pick a state, write a recurrence, and evaluate it bottom-up (tabulation) or top-down (memoization).

In any flow network the value of a maximum s - t flow equals the capacity of a minimum s - t cut; a flow is maximum exactly when its residual graph has no augmenting path, which is how Ford-Fulkerson finds it.

A problem is NP-complete when it is both in NP and NP-hard; under the assumption P ≠ NP such problems have no polynomial-time algorithm, and we prove hardness by a polynomial-time reduction from a known hard problem like SAT, Knapsack, or TSP.

Trace BFS (queue) and DFS (stack/recursion) deterministically by breaking every tie in alphabetical order — and read off the first/last vertex visited.

Dijkstra finalizes vertices in increasing distance order; each time one is extracted, it relaxes all of that vertex's outgoing edges — so the edge-relaxation sequence is dictated by the extract-min order.

Find the order of the VALUE a loop prints — not its running time — by turning the nested loops into a closed-form sum or product and reading off its leading power.

P is the set of languages decided by ONE algorithm in ONE fixed polynomial time bound for ALL inputs — the order ∃A ∃c ∀x is what makes it polynomial.

On an array of size n, Quicksort's comparison count is a random quantity ranging from nlog n (best) to n(n-1)/2 (worst), determined entirely by how each pivot splits its subarray.

Checking whether a claimed list of probes is the exact sequence a binary search would make costs only Θ(n) — replay the deterministic search and compare, never re-sort or re-search.

Bellman-Ford relaxes every edge n-1 times to settle all shortest paths; a single extra (n-th) pass that still relaxes an edge proves a negative cycle is reachable.

Bubble sort (and any sort that only swaps adjacent out-of-order elements) performs exactly as many swaps as there are inversions in the input — so you can count swaps without simulating the passes.

Bubble, selection, and insertion sort all run in Theta(n^2) on a random array; what distinguishes them is whether their cost depends on the input — selection sort is always Theta(n^2), bubble and insertion can drop to Theta(n) on sorted data.

Sort an array of three distinct key values into low-mid-high order in a single linear, in-place pass using three pointers.

Computing x^n with the four basic operations needs only Θ(log n) multiplications, not Θ(n) : repeatedly square the base while halving the exponent, multiplying in an extra x whenever a bit of n is 1 .

The greedy "take the largest coin that fits" rule for making change is not always optimal — it works only for canonical denomination systems. On a non-canonical set like 10,7,2,1 , greedy can use more coins than the true minimum.

To rank functions slowest-to-fastest, first unmask the impostors: rewrite each as a power of 2 via n=2^(log n) . Some "functions" are secretly constants, and log^()n grows slower than any iterated logarithm.

The cost of a loop is the SUM of the work each iteration does, not (iterations) x (max cost). When the body costs a constant, the sum collapses to (count) x O(1); when the body cost varies with i, evaluate the series. Split a loop with several statements into separate sums and add them.

The cost of a single counted loop is set by how the counter is UPDATED, not how it is compared. Solve the recurrence on the counter, set it equal to the bound n, and invert: i+=c gives n/c steps, i=c gives log_c n steps, and i=ii gives log log n steps.

When the work to split/combine, f(n) , exactly matches the leaf cost n^(log_b a) , the recurrence T(n)=aT(n/b)+f(n) solves to Θ (n^(log_b a)log n) — every level costs the same, and there are Θ(log n) levels.

Model one run of merge sort as a recursion tree with n leaves: there are n-1 internal (splitting) nodes, so merge is called n-1 times, total mergesort invocations are 2n-1, and the worst-case element comparisons are at most nceil(log2 n) - 2^ceil(log2 n) + 1. Don't confuse 'total calls' with 'recursive calls'.

Stopping merge-sort recursion at blocks of a constant size k and finishing each block with insertion sort keeps the running time at Θ(nlog n) ; the cutoff only shaves a constant factor. The bound changes only when k is allowed to grow with n .

When the recurrence feeds its own output back into itself, like G(n)=n-G(G(n-1)), unroll a few terms and look for a golden-ratio floor closed form.

When a recurrence shrinks n by a constant factor (e.g. n→ n/2 or n→√n ), the substitution n=2^m converts division into subtraction, turning a hard recurrence in n into an easy one in m that you can unroll or hit with the Master Theorem.

A sorted array cyclically rotated by some unknown amount still hides enough order to binary-search it in Θ(log n) : there is exactly one "drop" where A[i]>A[i+1] , and at every midpoint one half is guaranteed sorted, so you can find the pivot, the minimum, the maximum, or any target in logarithmic time.

Matrix multiplication is associative but its scalar-multiplication cost is not, so dynamic programming over interval splits finds the cheapest parenthesization in Θ(n^3) time.

LSD radix sort is correct only if the per-digit auxiliary sort is stable, so heapsort and quicksort cannot be plugged in while stable counting sort can.

Sort items by value-to-weight ratio and fill the knapsack greedily, taking a fraction of the last item; this is provably optimal for the fractional knapsack, unlike 0/1.

Schedule unit-time jobs for maximum profit by taking them in decreasing-profit order and placing each in the latest free slot before its deadline — provably optimal because the feasible sets form a matroid.