-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathalgorithm-complexity.html
More file actions
61 lines (59 loc) · 29 KB
/
algorithm-complexity.html
File metadata and controls
61 lines (59 loc) · 29 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Algorithm Complexity</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Big-Theta notation, Comparison of the asymptotic notations, Big-Omega Notation">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Algorithm Complexity">
<meta property="og:description" content="Big-Theta notation, Comparison of the asymptotic notations, Big-Omega Notation">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/algorithm-complexity.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Algorithm Complexity">
<meta name="twitter:description" content="Big-Theta notation, Comparison of the asymptotic notations, Big-Omega Notation">
<meta name="twitter:url" content="/algorithm/algorithm-complexity.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/14.a4b528fb.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" aria-current="page" class="active sidebar-link">Algorithm Complexity</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/algorithm-complexity.html#big-theta-notation" class="sidebar-link">Big-Theta notation</a></li><li class="sidebar-sub-header"><a href="/algorithm/algorithm-complexity.html#comparison-of-the-asymptotic-notations" class="sidebar-link">Comparison of the asymptotic notations</a></li><li class="sidebar-sub-header"><a href="/algorithm/algorithm-complexity.html#big-omega-notation" class="sidebar-link">Big-Omega Notation</a></li></ul></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="algorithm-complexity"><a href="#algorithm-complexity" class="header-anchor">#</a> Algorithm Complexity</h1> <h2 id="big-theta-notation"><a href="#big-theta-notation" class="header-anchor">#</a> Big-Theta notation</h2> <p>Unlike Big-O notation, which represents only upper bound of the running time for some algorithm, Big-Theta is a tight bound; both upper and lower bound. Tight bound is more precise, but also more difficult to compute.</p> <p>The Big-Theta notation is symmetric: <code>f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))</code></p> <p>An intuitive way to grasp it is that <code>f(x) = Ө(g(x))</code> means that the graphs of f(x) and g(x) grow in the same rate, or that the graphs 'behave' similarly for big enough values of x.</p> <p>The full mathematical expression of the Big-Theta notation is as follows:<br>
Ө(f(x)) = {g: N<sub>0</sub> -> R and c<sub>1</sub>, c<sub>2</sub>, n<sub>0</sub> > 0, where c<sub>1</sub> < abs(g(n) / f(n)), for every n > n<sub>0</sub> and abs is the absolute value }</p> <p><strong>An example</strong></p> <p>If the algorithm for the input <code>n</code> takes <code>42n^2 + 25n + 4</code> operations to finish, we say that is <code>O(n^2)</code>, but is also <code>O(n^3)</code> and <code>O(n^100)</code>. However, it is <code>Ө(n^2)</code> and it is not <code>Ө(n^3)</code>, <code>Ө(n^4)</code> etc. Algorithm that is <code>Ө(f(n))</code> is also <code>O(f(n))</code>, but not vice versa!</p> <p><strong>Formal mathematical definition</strong></p> <p><code>Ө(g(x))</code> is a set of functions.</p> <p><code>Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}</code></p> <p>Because <code>Ө(g(x))</code> is a set, we could write <code>f(x) ∈ Ө(g(x))</code>
to indicate that <code>f(x)</code> is a member of <code>Ө(g(x))</code>. Instead, we will usually write
<code>f(x) = Ө(g(x))</code> to express the same notion - that's the common way.</p> <p>Whenever <code>Ө(g(x))</code> appears in a formula, we interpret it as standing for some anonymous function that we do not care to name. For example the equation <code>T(n) = T(n/2) + Ө(n)</code>, means <code>T(n) = T(n/2) + f(n)</code> where <code>f(n)</code> is a function in the set <code>Ө(n)</code>.</p> <p>Let <code>f</code> and <code>g</code> be two functions defined on some subset of the real numbers. We write <code>f(x) = Ө(g(x))</code> as <code>x->infinity</code> if and only if there are positive constants <code>K</code> and <code>L</code> and a real number <code>x0</code> such that holds:</p> <p><code>K|g(x)| <= f(x) <= L|g(x)|</code> for all <code>x >= x0</code>.</p> <p>The definition is equal to:</p> <p><code>f(x) = O(g(x)) and f(x) = Ω(g(x))</code></p> <p><strong>A method that uses limits</strong></p> <p>if <code>limit(x->infinity) f(x)/g(x) = c ∈ (0,∞)</code> i.e. the limit exists and it's positive, then <code>f(x) = Ө(g(x))</code></p> <p><strong>Common Complexity Classes</strong></p> <table><thead><tr><th>Name</th> <th>Notation</th> <th>n = 10</th> <th>n = 100</th></tr></thead> <tbody><tr><td>Constant</td> <td>Ө(1)</td> <td>1</td> <td>1</td></tr> <tr><td>Logarithmic</td> <td>Ө(log(n))</td> <td>3</td> <td>7</td></tr> <tr><td>Linear</td> <td>Ө(n)</td> <td>10</td> <td>100</td></tr> <tr><td>Linearithmic</td> <td>Ө(n*log(n))</td> <td>30</td> <td>700</td></tr> <tr><td>Quadratic</td> <td>Ө(n^2)</td> <td>100</td> <td>10 000</td></tr> <tr><td>Exponential</td> <td>Ө(2^n)</td> <td>1 024</td> <td>1.267650e+ 30</td></tr> <tr><td>Factorial</td> <td>Ө(n!)</td> <td>3 628 800</td> <td>9.332622e+157</td></tr></tbody></table> <h2 id="comparison-of-the-asymptotic-notations"><a href="#comparison-of-the-asymptotic-notations" class="header-anchor">#</a> Comparison of the asymptotic notations</h2> <p>Let <code>f(n)</code> and <code>g(n)</code> be two functions defined on the set of the positive real numbers, <code>c, c1, c2, n0</code> are positive real constants.</p> <table><thead><tr><th>Notation</th> <th>f(n) = O(g(n))</th> <th>f(n) = Ω(g(n))</th> <th>f(n) = Θ(g(n))</th> <th>f(n) = o(g(n))</th> <th>f(n) = ω(g(n))</th></tr></thead> <tbody><tr><td>Formal definition</td> <td><code>∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ c g(n)</code></td> <td><code>∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c g(n) ≤ f(n)</code></td> <td><code>∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)</code></td> <td><code>∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < c g(n)</code></td> <td><code>∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c g(n) < f(n)</code></td></tr> <tr><td>Analogy between the asymptotic comparison of <code>f, g</code> and real numbers <code>a, b</code></td> <td><code>a ≤ b</code></td> <td><code>a ≥ b</code></td> <td><code>a = b</code></td> <td><code>a < b</code></td> <td><code>a > b</code></td></tr> <tr><td>Example</td> <td><code>7n + 10 = O(n^2 + n - 9)</code></td> <td><code>n^3 - 34 = Ω(10n^2 - 7n + 1)</code></td> <td><code>1/2 n^2 - 7n = Θ(n^2)</code></td> <td><code>5n^2 = o(n^3)</code></td> <td><code>7n^2 = ω(n)</code></td></tr> <tr><td>Graphic interpretation</td> <td><a href="https://i.stack.imgur.com/AkEKr.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/AkEKr.png" alt="O-notation"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></td> <td><a href="https://i.stack.imgur.com/5qDtj.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/5qDtj.png" alt="Ω-notation"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></td> <td><a href="https://i.stack.imgur.com/RPdzC.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/RPdzC.png" alt="Θ-notation"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></td> <td></td> <td></td></tr></tbody></table> <p>The asymptotic notations can be represented on a Venn diagram as follows:
<a href="https://i.stack.imgur.com/v2eH3.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/v2eH3.png" alt="Asymptotic notations"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <h3 id="links"><a href="#links" class="header-anchor">#</a> Links</h3> <p>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms.</p> <h2 id="big-omega-notation"><a href="#big-omega-notation" class="header-anchor">#</a> Big-Omega Notation</h2> <p>Ω-notation is used for asymptotic lower bound.</p> <h3 id="formal-definition"><a href="#formal-definition" class="header-anchor">#</a> Formal definition</h3> <p>Let <code>f(n)</code> and <code>g(n)</code> be two functions defined on the set of the positive real numbers. We write <code>f(n) = Ω(g(n))</code> if there are positive constants <code>c</code> and <code>n0</code> such that:</p> <p><code>0 ≤ c g(n) ≤ f(n) for all n ≥ n0</code>.</p> <h3 id="notes"><a href="#notes" class="header-anchor">#</a> Notes</h3> <p><code>f(n) = Ω(g(n))</code> means that <code>f(n)</code> grows asymptotically no slower than <code>g(n)</code>.
Also we can say about <code>Ω(g(n))</code> when algorithm analysis is not enough for statement about <code>Θ(g(n))</code> or / and <code>O(g(n))</code>.</p> <p>From the definitions of notations follows the theorem:</p> <p>For two any functions <code>f(n)</code> and <code>g(n)</code> we have <code>f(n) = Ө(g(n))</code> if and only if
<code>f(n) = O(g(n)) and f(n) = Ω(g(n))</code>.</p> <p>Graphically Ω-notation may be represented as follows:</p> <p><a href="https://i.stack.imgur.com/5qDtj.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/5qDtj.png" alt="Ω-notation"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>For example lets we have <code>f(n) = 3n^2 + 5n - 4</code>. Then <code>f(n) = Ω(n^2)</code>. It is also correct <code>f(n) = Ω(n)</code>, or even <code>f(n) = Ω(1)</code>.</p> <p>Another example to solve perfect matching algorithm : If the number of vertices is odd then output "No Perfect Matching" otherwise try all possible matchings.</p> <p>We would like to say the algorithm requires exponential time but in fact you cannot prove a <code>Ω(n^2)</code> lower bound using the usual definition of <code>Ω</code> since the algorithm runs in linear time for n odd. We should instead define <code>f(n)=Ω(g(n))</code> by saying for some constant <code>c>0</code>, <code>f(n)≥ c g(n)</code> for infinitely many <code>n</code>. This gives a nice correspondence between upper and lower bounds: <code>f(n)=Ω(g(n))</code> iff <code>f(n) != o(g(n))</code>.</p> <h3 id="references"><a href="#references" class="header-anchor">#</a> References</h3> <p>Formal definition and theorem are taken from the book "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms".</p> <h4 id="remarks"><a href="#remarks" class="header-anchor">#</a> Remarks</h4> <p>All algorithms are a list of steps to solve a problem. Each step has dependencies on some set of previous steps, or the start of the algorithm. A small problem might look like the following:</p> <p><a href="https://i.stack.imgur.com/qP043.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/qP043.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>This structure is called a directed acyclic graph, or DAG for short. The links between each node in the graph represent dependencies in the order of operations, and there are no cycles in the graph.</p> <p>How do dependencies happen? Take for example the following code:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>total <span class="token operator">=</span> <span class="token number">0</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token number">10</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
total <span class="token operator">=</span> total <span class="token operator">+</span> i
</code></pre></div><p>In this psuedocode, each iteration of the for loop is dependent on the result from the previous iteration because we are using the value calculated in the previous iteration in this next iteration. The DAG for this code might look like this:</p> <p><a href="https://i.stack.imgur.com/7zrQI.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/7zrQI.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>If you understand this representation of algorithms, you can use it to understand algorithm complexity in terms of work and span.</p> <h3 id="work"><a href="#work" class="header-anchor">#</a> Work</h3> <p>Work is the actual number of operations that need to be executed in order to achieve the goal of the algorithm for a given input size <code>n</code>.</p> <h3 id="span"><a href="#span" class="header-anchor">#</a> Span</h3> <p>Span is sometimes referred to as the critical path, and is the fewest number of steps an algorithm must make in order to achieve the goal of the algorithm.</p> <p>The following image highlights the graph to show the differences between work and span on our sample DAG.</p> <p><a href="https://i.stack.imgur.com/LD7PU.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/LD7PU.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>The work is the number of nodes in the graph as a whole. This is represented by the graph on the left above. The span is the critical path, or longest path from the start to the end. When work can be done in parallel, the yellow highlighted nodes on the right represent span, the fewest number of steps required. When work must be done serially, the span is the same as the work.</p> <p>Both work and span can be evaluated independently in terms of analysis. The speed of an algorithm is determined by the span. The amount of computational power required is determined by the work.</p></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/algorithm-complexity.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/getting-started-with-algorithm.html" class="prev">
Getting started with algorithm
</a></span> <span class="next"><a href="/algorithm/big-o-notation.html">
Big-O Notation
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/14.a4b528fb.js" defer></script>
</body>
</html>