1x
go to beginning previous frame pause play next frame go to end

This visualization can visualize the recursion tree of any recursive algorithm or the recursion tree of a Divide and Conquer (D&C) algorithm recurrence (e.g., Master Theorem) that we can legally write in JavaScript.


We can also visualize the Directed Acyclic Graph (DAG) of a Dynamic Programming (DP) algorithm and compare the dramatic search-space difference of a DP problem versus when its overlapping sub-problems are naively recomputed, e.g., the exponential Ω(2n/2) recursive Fibonacci versus its O(n) DP version.


On some problems, we can also visualize the difference between what a Complete Search (recursive backtracking) that explores the entire search space, a greedy algorithm (that greedily picks one branch each time), versus Dynamic Programming look like in the same recursion tree, e.g., Coin-Change of v = 7 cents with 4 coins {4, 3, 1, 5} cents.


Most recursion trees require large drawing space, therefore view this visualization page on a large screen. For obvious reason, we cannot really visualize very big trees/DAGs. Therefore, we call our recursion with small parameter(s).


Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑

This is the Recursion Tree and Recursion Directed Acyclic Graph (DAG) visualization area. The Recursion Tree/DAG are drawn/animated as per how a real computer program that implements this recursion works, i.e., "depth-first".


The recursion starts from the initial state that is colored dark brown. The current parameter value is shown inside each vertex (comma-separated for recursion with two or more parameters). Active vertices will be colored orange. Vertices that are no longer calling any other recursive problem (the base cases) will be colored green. Vertices (subproblems) that are repeated will be colored lightblue for the second occurrence onwards. The return value of each recursive call is written as a red text below the vertex. This visualization is generic for any recursion that you can legally write in JavaScript.


Note that due to combinatorial explosion, it will be very hard to visualize the Recursion Tree for large instances.


Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑

For the Recursion DAG, it will also very hard to minimize the number of edge crossings in the event of overlapping subproblems. However, we try our best to give a custom DAG drawing layout for certain DP problems to improve the presentation.


For example, we currently show the recursion DAG of the computation of the n-th Fibonacci number. We layout the vertices from leftmost (the two green-colored base cases n = 0 and n = 1) to rightmost (the initial n). Ideally this is shown as a flat 1-D (memoization) array. However as VisuAlgo does not have curvy edge yet, we decided to put odd-numbered vertices slightly below the even-numbered vertices to get around the overlapping edges issue. To compute fib(n), we only need to know the result of two immediate results: fib(n-1) + fib(n-2) that is depicted as the two arrows from vertex n to vertices n-1 and n-2. The results of the summation, i.e., the values of each fib(n), are displayed as red text below the vertices. As there is no repeated subproblem computation, there is no lightblue vertex at all in this recursion DAG (such vertices/states will have more than one incoming arrows instead).


Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

🕑

Select one of the example recursive algorithms in the drop-down list or write our own recursive code — in JavaScript. The final recursion Tree / DAG is immediately displayed. Note that this visualization can run any JavaScript code, including malicious code, so please be careful (it will only affect your own web browser, don't worry).


Click the 'Run' button at the top right corner of the action box to start the step-by-step visualization of the recursive function after you have selected (or written) a valid JavaScript code!


In the next sub-sections, we start with example recursive algorithms with just one sub-problem, i.e., not branching. For these one-subproblem examples, their recursion trees and recursion DAGs are 100% identical (they looked like Singly Linked Lists from the root (initial call) to the leaf (base case)). As there is no overlapping subproblem for the examples in this category, you will not see any lightblue-colored vertex and only one green-colored vertex (the base case). The default orientation for recursion Tree is top-right-to-bottom-left whereas the default orientation for recursion DAG is right-to-left.


Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

The Factorial Numbers example computes the factorial of an integer n.


f(n) = 1 (if n == 0);
f(n) = n*f(n-1) otherwise


It is one of the simplest (tail) recursive function that can be easily rewritten into an iterative version. It's time complexity is also simply Θ(n).


The value of Factorial f(n) grows very fast, thus try only the small integers n ∈ [0..10]
(we randomize the value of the initial n between this range).

🕑

The Binary Search example finds the index of a2 in a sorted array a1[a..b]. We start binary search from the initial search space of a=0,b=a1.length-1 (the entire array a1, with n = (a1.length-1) - 0 + 1 = a1.length).


f(a,b) = -1 (if a > b);
let mid = floor((a+b)/2);
f(a,b) = mid (if a2 = a1[mid]);
f(a,b) = f(a,mid-1) (if a2 < a1[mid]);
f(a,b) = f(mid+1,b) (if a2 > a1[mid]);


Only one of the two possible branches will be executed each time, resulting in a recursion tree = recursion DAG situation. The time complexity if Θ(log n) as we keep halving the search space each time. The worst-case happens when a2 is not found in sorted array a1.


In this visualization, we randomize the content of sorted array a1 and the value to be searched a2.


TBC: In the near future, we will draw the entire Θ(n) search space (both left and right branches at each vertex) and highlight the efficient Θ(log n) path taken by Binary Search on this search space. This is like seeing the animation of Search(v) function of a (balanced) Binary Search Tree.

🕑

The Modulo Power example computes the a1^p % a2 in efficient way.


f(p) = 1 (if p == 0);
f(p) = f(floor(p/2))^2 % a2 (if p is even)
f(p) = f(floor(p/2))^2 * a1 % a2 (if p is odd)


This Divide & Conquer (D&C) algorithm runs in Θ(log p).


In this visualization, we randomize the values of a1 (the base, a small value ∈ [2..4]),
a2 (the modulo, a prime ∈ [7, 97, 997, 9973]), and power p (we want to raise a1 to its p-th power, modulo a2. Due to its low time complexity, it is OK to try very large 0 ≤ p ≤ 256.


TBC: In the near future, we may draw the comparison between this efficient D&C modulo power algorithm with the naive version that multiply a1 p times that runs in Θ(p).

🕑

The Greatest Common Divisor (GCD) example computes the GCD of two integers a and b.


f(a, b) = a (if b == 0);
f(a, b) = f(b, a%b) otherwise


This is the classic Euclid's algorithm that runs in O(log n) where n = min(a, b) — depending of the details, n = max(a, b) or n = a+b are also possible.


Euclid's algorithm is an example of Divide & Conquer (D&C) algorithm.


Due to its low time complexity, it should be OK to try 0 ≤ a, b ≤ 99.
(we randomize the values of a and b between this range and set a ≥ b).
Note that if we put a < b, technically the first recursive step will swap a and b.


Do explore various possible combinations of a and b and notice on what values f(a, b) terminates very quickly in 1 step (b = 0), 2 steps (b = gcd(a, b)), or the maximum number of steps (try this sequence) — to show the lowerbound Ω(log n).

🕑

The Max Range Sum example computes the value of the subarray with the maximum total sum inside the given (global) array a1 with n = a1.length integers (the first textbox below the code editor textbox). The value of a1 can be positive integers, zeroes, or negative integers (without negative integer, the answer will obviously the sum of the entire integers in a1).


Formally, let's define RSQ(i, j) = a1[i] + a1[i+1] + ... + a1[j], where 0 ≤ i ≤ j ≤ n-1 (RSQ stands for Range Sum Query). Max Range Sum problem seeks to find the optimal i and j such that RSQ(i, j) is the maximum.


f(i) = max(ai[0], 0) (if i == 0, as ai[0] can be negative);
f(i) = max(f(i-1) + ai[i], 0) otherwise


We call f(n-1). The largest value of f(i) is the answer.


This is the classic Kadane's algorithm that runs in O(n).

🕑

The Catalan example computes the n-th Catalan number recursively.


f(n) = 1 (if n == 0);
f(n) = f(n-1)*2*n*(2*n-1)/(n+1)/n; otherwise


This explanation is a stub that will be expanded later.

🕑

In the next sub-sections, we will see example recursive algorithms that have exactly two sub-problems, i.e., branching. The sizes of the subproblems can be identical or vary. For these two sub-problems examples, their recursion trees will usually be much bigger that their recursion DAGs (especially if there are (many) overlapping sub-problems, indicated with the lightblue vertices on the recursion tree drawing).


Currently shown on screen is the recursion tree of a Fibonacci recurrence.

🕑

The Fibonacci Numbers example computes the n-th Fibonacci number.


f(n) = n (if n <= 1); // i.e., 0 if n == 0 or 1 if n == 1
f(n) = f(n-1) + f(n-2) otherwise


Unlike Factorial example, this time each recursive step recurses to two other smaller sub-problems (if we call f(n-1) first before f(n-2), then the left side of the recursion tree will be taller than the right side — try swapping the two sub-problems).


The value of Fibonacci f(n) grows very fast and its recursion tree — if implemented verbatim as defined above — also grows exponentially, i.e., at least Ω(2n/2), thus try only the small initial values of n ≤ 7 (to avoid crashing your web browser).


Fibonacci recursion tree is frequently used to showcase the basic idea of recursion, its inefficiency (due to the many overlapping subproblems), and the linkage to Dynamic Programming (DP) topic.

🕑

The recursion DAG (shown in the background) of Fibonacci computation only contains O(n) vertices and thus can go to a larger n ≤ 30 (so it still looks nice in this visualization; in practice n can go to millions with this DP solution).


Most of the time, the Fibonacci computation is written in iterative fashion after one understands the concept of DP.


It is probably rare to think this way, but this visualization shows that the computation of Fibonacci f(n) is basically counting the number of paths from n to vertex 1.

🕑

The C(n, k) example computes the binomial coefficient C(n, k).


f(n, k) = 1 (if k == 0); // 1 way to take nothing out of n items
f(n, k) = 1 (if k == n); // 1 way to take everything out of n items
f(n, k) = f(n-1, k-1) + f(n-1, k) // take the last item or skip it


The recursion tree of C(n, k) grows very fast, with the largest tree when k = n/2, smaller trees when k is close to 0 or n (a few path(s) with short leafs), and smallest trees when k is 0 or n (only one vertex).

🕑

The recursion DAG of C(n, k) is basically an inverted Pascal's Triangle. It only contains O((n/2)*(n/2)) = O(n^2/4) vertices at most (when k = n/2) although in practice we probably just use a DP/memo table of size O(n^2). Thus we can go to a larger n ≤ 15 (so it still looks nice in this visualization) and k∈[0..n], including when k≈n/2.


TBC: In the near future, we may draw a dummy vertex (0, 0) --- C(n, k) will not actually reach it unless started from C(0, 0) with return value of 1 to complete the inverted Pascal's Triangle visualization.

🕑

The 0-1 Knapsack example solves the 0/1 Knapsack Problem: What is the maximum value that we can get, given a knapsack that can hold a maximum weight of w, where the value of the i-th item is a1[i], the weight of the i-th item is a2[i]?


0-1 Knapsack has a classic DP recurrence f(i, w) which we call using f(n-1, max-w) where n = a1.length.


f(i, w) = f(i-1, w); // ignore item i (always possible)
f(i, w) = a1[i] + f(i-1, w-a2[i]); // take item i (if a2[i] <= w)
f(<0, w) = 0; // all items have been considered
f(i, 0) = 0; // cannot carry anything else


The recursion tree of this DP recurrence has a few (like currently shown on screen) to many (e.g., try all items having the same weight, i.e., ones) overlapping sub-problems.

🕑

The recursion DAG of 0-1 Knapsack only contains O(n * max-w) vertices. Thus we can go to a larger n ≤ 7 and max-w ≤ 15 (so it still looks nice in this visualization).


This DP recurrence basically tries to find the longest (weighted) path in this implicit DAG and has time complexity of O(n * max-w).


If the weights of each item in a2 vary a lot, the recursion DAG will look sparse. Try setting a2=[1,2,...,2^i] for a denser recursion DAG> (but no overlap) or a2=[1,1,...,1] (lots of overlap).

🕑

In the next sub-sections, we will see example recursive algorithms that have many sub-problems (1, 2, 3, ..., a certain limit). For many of these examples, the sizes of their Recursion Trees are exponential and we will really need to use Dynamic Programming to compute its Recursion DAGs instead.

🕑

The Longest Increasing Subsequence example solves the Longest Increasing Subsequence problem: Given an array a1, how long is the Longest Increasing Subsequnce of the array?


The recursion DAG of the default example (not randomized) is as follows: Vertex j ∈ [0..i-1] is laid out horizontally (along the x-axis from left/vertex 0 to right/vertex i-1), then placed vertically (along the y-axis according to the value of a1[j]). We draw an edge between two indices j and k if a1[j] < a1[k] (with all vertices having hidden edge to the dummy max(a1)+1 value at the top-right cell so that all LIS ends at this dummy vertex and we can start the recursion with f(i) where i = a1.length-1). Then this LIS problem can be visualized as finding the longest path in this (implicit) recursion DAG.


As there are |V| = n vertices and |E| = O(n^2) edges (use sorted ascending test case, e.g., {1,2,4,8,16,...} to have nice visualization), the overall time complexity to solve LIS using DP is O(n^2). Since early 2000s, we should use the faster O(n log k) greedy+binary search solution for LIS (not explained in this slide).

🕑

The Coin Change example solves the Coin Change problem: Given a list of coin values in a1, what is the minimum number of coins needed to get the value v?


The recursion tree of the default example (not randomized) has v = 7 cents and 4 coins that are specifically selected to be {4, 3, 1, 5}. What is shown on-screen is the entire recursion tree of Coin-Change recursive function.


A typical greedy algorithm for Coin-Change that always take the largest coin value that does not exceed current value v will be trapped into taking the rightmost branch: 7 cents (take 5 cents coin) → 2 cents (take 1 cent coin) → 1 cent (take another 1 cent coin) → 0 (total 3 coins).


DP algorithm that explores this recursion tree (but avoiding repeated computations on the lightblue vertices will find the lefmost branch: 7 cents (take 4 cents coin) → 3 cents (take 3 cents coin) → 0 (total 2 coins). Alternative solution: 7 → 4 → 0 (also 2 coins).

🕑

The Cutting Rod example solves the 'fictional' introductory problem in Chapter 14.1 - Dynamic Programming of the "Introductions to Algorithms" (CLRS 4th edition) textbook: Given a rod of length n inches and a table of prices a1 for length 1,2,...,n inches, determine the maximum revenue obtainable by cutting up the rod and selling the pieces.


The recursion tree of the default example (not randomized) has n = 4 inches. What is shown on-screen is the entire recursion tree of Cut-Rod recursive function.


f(n) = max(a1[i-1] + f(n-i)) ∀i∈[1..n];
f(0) = 0; // cannot cut anymore
🕑

The Matrix Chain Mult(iplication) example solves the second DP introductory problem in Chapter 14.2 of the "Introductions to Algorithms" (CLRS 4th edition) textbook: Given a sequence (chain) of n = a1.length-1 matrices to be multiplied, where the matrices aren't necessarily square, compute the product A1*A2*...*An using the standard O(p*q*r) algorithm for multiplying rectangular matrices, while minimizing the number of scalar multiplications.


The recursion tree of the default example (not randomized) has i=1,j=4. What is shown on-screen is the entire recursion tree of MCM recursive function.


f(i,j) = min(f(i,k)+f(k+1,j)+a1[i-1]*a1[k]*a1[j]) ∀i≤k<j;
f(i,j) = 0 if i == j; // no need to multiply a single matrix
🕑

The Longest Common Subsequence (LCS) example solves the Longest Common Subsequence problem: Given two strings (character arrays) a1 (of length n = a1.length) and a2 (of length m = a2.length), how long is the Longest Common Subsequence between the two strings?


f(n, m) = 1 + f(n-1, m-1); // if a1[n] == a2[m]; last char matches
f(n, m) = max(f(n-1, m), f(n, m-1)) // if last char differs
f(n, <0) = 0; // a2 is empty
f(<0, m) = 0; // a1 is empty


We call f(n-1, m-1), from the last character of both strings.


The recursion tree of this DP recurrence has an exponential (like currently shown on screen) number of overlapping sub-problems if both strings have many different characters (but do try a1 == a2; we will see a single-branch recursion tree).

🕑

The recursion DAG of LCS only contains O(n * m) vertices. Thus we can use longer strings with n ≤ 10 and m ≤ 10 (so it still looks nice in this visualization).


This DP recurrence basically tries to find the longest (0/1-weighted) path in this implicit DAG and has time complexity of O(n * m).

🕑

The Graph Matching problem computes the maximum number of matching on a small graph, which is given in the adjacency matrix a1.


This slide is a stub and will be expanded in the future.

🕑

The Traveling Salesperson example solves the Traveling Salesperson Problem on small graph: How long is the shortest path that goes from city 0, passes through every city once, and goes back again to 0? The distance between city i and city j is denoted by a1[i][j].


This slide is a stub and will be expanded in the future.

🕑

In the next sub-sections, instead of visualizing the recursion tree of a recursive algorithm, we visualize the recursion tree of the recurrence (equation) to help analyze the time complexity of certain Divide and Conquer (D&C) algorithms.


The value computed by f(n) (the red label underneath each vertex that signifies the return value of that recursive function/that subproblem) is thus the total number of operations taken by that recursive algorithm when its problem size is n (the value drawn inside each vertex). Most textbooks will say the function name of this recurrence as T(n), but we choose not to change our default f(n) function name that is used in all other recursive algorithm visualizations. Some other textbooks (e.g., CLRS) also put the cost of each vertex only, not the cost of the entire subproblem.

🕑

In Sorting visualization, we learn about merge sort. It's time complexity recurrences are:


f(n) = Θ(1) (if n < n0) — we usually assume that the base cases are Θ(1)
f(n) = f(n/2) + f(n/2) + c*n (otherwise)

Please check the recursion tree of the default example (n = 16). We will use the same recursion tree for the next few sub-slides. You should see the initial problem size of n = 16 written inside the root vertex and its return value (total amount of work done by f(16) is 32+32+1*16 = 80). This value of f(n) is consistent throughout the recursion tree, e.g., f(8) = f(4)+f(4)+1*4 = 12+12+1*8 = 32.

🕑

我们看到这个递归树的高度是 log2 n 因为我们一直将 n 除以 2 直到我们达到大小为 1 的基本情况。


对于 n = 16,我们有16->8->4->2->1 (log2 16 = 4 步)。


PS: 树的高度 = 从根到最深叶子的边的数量。

🕑

As the effort done in the recursive step per subproblem of size n is c*n (the divide (trivial, Θ(1)) and the conquer (merge) operation, the Θ(n)), we will perform exactly c*n operations per each recursion level of this specific recursion tree.


The root of size (n) does c*n operations during the merge step.
The two children of the root of size (n/2) both do c*n/2, and 2*c*n/2 = c*n too.
The grandchildren level is 4*c*n/4 = c*n too.
And so on until the last level (the leaves).


As the red label underneath each vertex in this visualization reports the value of the entire subproblem (including the subtrees below), these identical costs per level are not easily seen, e.g., from root to leaf, we see 80, 2x32 = 64, 4x12 = 48, 8x4 = 32, 16x1 = 16 and may get different conclusion... However, if we discounted the values of its subproblems, we will get the same conclusion, e.g., for the root, we do 80-2x32 = 16 operations, for the children of the root, we do 2x(32-2x12) = 2x8 = 16 operations too, etc.


Soon, we will show 'work-done-in-each-level' info in the visualization directly.

🕑

绿色叶子的数量是 2log2 n = nlog2 2 = n。


这些叶子每个都做 Θ(1) 步,因此最后一层(叶子层)的总工作量也是 Θ(n)。


因此,归并排序所做的总工作量是每层 c*n,乘以递归树的高度(log2 n + 1 更多的叶子),或 Θ(n log n)。


对于这个例子,f(16) = 80 来自 1x16 x (log2 16 + 1) = 16 x (4 + 1) = 16 x 5 = 80。

🕑

In Sorting visualization, we also learn about the non-random(ized) quick sort.


It may have a worst case behavior of O(n2) on certain kind of (trivial) instances of (nearly-) sorted input and it may have the following time complexity recurrence (with a = 1):


f(n) = Θ(1) (if n < n0) — we usually assume that the base cases are Θ(1)
f(n) = f(n-a) + f(a) + c*n (otherwise)

Note that writing the recurrence in the other direction does not matter much asymptotically, other than the recursion tree will be mirrored.


Please observe the currently drawn recursion tree.
We want to show that this recursion tree has f(n) = O(n2).

🕑

We see that
the height of
this recursion tree
is rather tall, i.e., n/a - 1
as we only reduces n
by a per level.
Thus, we need n/a - 1 steps
to reach the base case
(n = 1).


For n = 16, a = 1, we have
16->
15->
14->
...->
2->
1 (16/1 - 1 = 15 steps).

🕑

在每个大小为 n 的子问题的递归步骤中,我们所做的工作量是 c*n(在 Θ(n) 中划分(分区)操作;征服步骤是微不足道的 — Θ(1)),我们将在每个递归级别执行精确的 c*n 操作。


根的大小 (n) 在分区步骤中进行 c*n 操作。
根的子节点的大小 (n-a) 执行 c*(n-1),另一个执行 f(a)。
孙子级别执行 c*(n-2),另一个执行 f(a)。
等等,直到最后一级(叶子都执行 f(a))。

🕑

快速排序在这种最坏情况的输入上所做的总工作是等差级数1+2+...+n的总和,再加上一些其他常数因子操作(所有的f(a)都是Θ(1))。这简化为f(n) = Θ(n2)

🕑

For recurrences of the form:

f(n) = a*f(n/b) + g(n)

where a ≥ 1, b > 1, and g(n) is asymptotically positive,
we maybe able to apply the master theorem (also called as master method).
PS: In this visualization, we have to rename CLRS function names to our convention:
f(n) → g(n) and T(n) → f(n).


We compare the driving function g(n) (the amount of divide and conquer work in each recursive step of size n) with nlogba (the watershed function — also the asymptotic number of leaves of the recursion tree), if g(n) = O(nlogba) for ε > 0, it means that the driving function g(n) grows polynomially slower than the watershed function nlogba (by a factor of nε), thus the watershed function nlogba will dominate and the solution of the recurrence is f(n) = θ(nlogba).


Visually, if you see the recursion tree for recurrence that falls into case 1 category, the cost per level grows exponentially from root level to the leaves (in this picture, 1*4*4 = 16, 7*2*2 = 28, 49*1*1 = 49, ..., 16+28+49 = 93), and the total cost of the leaves dominates the total cost of all internal vertices.

🕑

The most popular example is Strassen's algorithm for matrix multiplication where case 1 of master theorem is applicable. The recurrence is: f(n) = 7*f(n/2) + c*n*n.


Thus a = 7, b = 2, watershed = nlog2 7 = n2.807, driving = g(n) = Θ(n2).


n2 = O(n2.807-ε) for ε = 0.807... — case 1 — Thus f(n) = Θ(n2.807)

Exercise: You can try changing the demo code by setting a = 8 and set g(n) = c*1 to change the recurrence of Strassen's algorithm to the recurrence of the simple recursive matrix multiplication algorithm that has f(n) = Θ(n3).

🕑

The detailed analysis of the Merge sort algorithm from a few slides earlier can be simplified using master theorem, e.g., f(n) = 2*f(n/2) + c*n.


Thus a = 2, b = 2, watershed = nlog2 2 = n, driving = g(n) = Θ(n).
n = Θ(n logk n) for k = 0
The watershed and driving functions have the same asymptotic growth — case 2
Thus f(n) = Θ(n log n).


Visually, if you see the recursion tree for recurrence that falls into case 2 category, the cost per level is ~the same, i.e., Θ(nlogba logk n) and there are logb n levels. We claim that the solution is f(n) = Θ(nlogba logk+1 n). That's it, the solution of the recurrence that falls under case 2 is to add an extra log factor to g(n).


Exercise: You can try changing the demo code by setting a = 1 and set g(n) = c*1 to change the recurrence of Merge sort algorithm to the recurrence of the binary search algorithm. For binary search version, f(n) = Θ(log n). Notice that for most of real-life case 2 algorithm recurrences (e.g., Merge Sort and Binary Search), k = 0.

🕑

Case 3 is the opposite of Case 1, where the driving function g(n) grows polynomially faster than the watershed function nlogba. Thus the bulk of the operations is done by the driving function at the root level (but check the regularity condition too, to be elaborated below). This case 3 is actually rarely appear in real algorithms so we use an example fictional recurrence: f(n) = 4*f(n/2) + c*n^3.


Thus a = 4, b = 2, watershed = nlog2 4 = n2, driving = g(n) = Θ(n3).
n^3 = Ω(n2+ε) for ε = 1 and
4*(n/2)3 ≤ c*n3 (regularity condition) for c = 1/2 — case 3
Thus f(n) = Θ(n3).


Visually, if you see the recursion tree for recurrence that falls into case 3 category, the cost per level drops exponentially from root level to the leaves (in this picture, 1*4*4*4 = 64, 4*2*2*2 = 32, 16*1*1*1 = 16, ..., 64+32+16 = 112), and the total cost of the root dominates the total cost of all other internal vertices (including the (many) leaves).


You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑
f(){
运行

}
var a1 =
var a2 =

>

开始

关于 团队 使用条款
隐私政策

关于

VisuAlgo最初由副教授Steven Halim于2011年构思,旨在通过提供自学、互动式学习平台,帮助学生更深入地理解数据结构和算法。

VisuAlgo涵盖了Steven Halim博士与Felix Halim博士、Suhendry Effendy博士合著的书《竞技编程》中讨论的许多高级算法。即使过去十年,VisuAlgo仍然是可视化和动画化这些复杂算法的独家平台。

虽然VisuAlgo主要面向新加坡国立大学(NUS)的学生,包括各种数据结构和算法课程(例如CS1010/等价课程,CS2040/等价课程(包括IT5003),CS3230,CS3233和CS4234),但它也是全球好奇心的宝贵资源,促进在线学习。

最初,VisuAlgo并不适用于智能手机等小触摸屏,因为复杂的算法可视化需要大量的像素空间和点击拖动交互。为了获得最佳用户体验,建议使用最低分辨率为1366x768的屏幕。然而,自2022年4月以来,VisuAlgo的移动(精简)版本已经推出,使得在智能手机屏幕上使用VisuAlgo的部分功能成为可能。

VisuAlgo仍然在不断发展中,正在开发更复杂的可视化。目前,该平台拥有24个可视化模块。

VisuAlgo配备了内置的问题生成器和答案验证器,其“在线测验系统”使学生能够测试他们对基本数据结构和算法的理解。问题根据特定规则随机生成,并且学生提交答案后会自动得到评分。随着越来越多的计算机科学教师在全球范围内采用这种在线测验系统,它可以有效地消除许多大学标准计算机科学考试中手工基本数据结构和算法问题。通过给通过在线测验的学生分配一个小但非零的权重,计算机科学教师可以显著提高学生对这些基本概念的掌握程度,因为他们可以在参加在线测验之前立即验证几乎无限数量的练习题。每个VisuAlgo可视化模块现在都包含自己的在线测验组件。

VisuAlgo已经被翻译成三种主要语言:英语、中文和印尼语。此外,我们还用各种语言撰写了关于VisuAlgo的公开笔记,包括印尼语、韩语、越南语和泰语:

id, kr, vn, th.

团队

项目领导和顾问(2011年7月至今)
Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

本科生研究人员 1
CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai

最后一年项目/ UROP学生 1
Jul 2012-Dec 2013: Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

本科生研究人员 2
CDTL TEG 2: May 2014-Jul 2014: Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

最后一年项目/ UROP学生 2
Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

本科生研究人员 3
Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

最后一年项目/ UROP学生 3
Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han

List of translators who have contributed ≥ 100 translations can be found at statistics page.

致谢
NUS教学与学习发展中心(CDTL)授予拨款以启动这个项目。在2023/24学年,Optiver的慷慨捐赠将被用来进一步开发 VisuAlgo。

使用条款

VisuAlgo慷慨地向全球计算机科学界提供免费服务。如果您喜欢VisuAlgo,我们恳请您向其他计算机科学学生和教师宣传它的存在。您可以通过社交媒体平台(如Facebook、YouTube、Instagram、TikTok、Twitter等)、课程网页、博客评论、电子邮件等方式分享VisuAlgo。

数据结构与算法(DSA)的学生和教师可以直接在课堂上使用本网站。如果您从本网站截取屏幕截图或视频,可以在其他地方使用,但请引用本网站的URL(https://visualgo.net)和/或下面的出版物列表作为参考。但请不要下载VisuAlgo的客户端文件并将其托管在您的网站上,因为这构成了抄袭行为。目前,我们不允许他人分叉此项目或创建VisuAlgo的变体。个人使用离线副本的客户端VisuAlgo是可以接受的。

请注意,VisuAlgo的在线测验组件具有重要的服务器端元素,保存服务器端脚本和数据库并不容易。目前,普通公众只能通过“培训模式”访问在线测验系统。“测试模式”提供了一个更受控制的环境,用于在新加坡国立大学的真实考试中使用随机生成的问题和自动验证。


出版物列表

这项工作曾在2012年国际大学生程序设计竞赛(波兰,华沙)的CLI研讨会上和2012年国际信息学奥林匹克竞赛(意大利,锡尔米奥内-蒙蒂基亚里)的IOI会议上展示过。您可以点击此链接阅读我们2012年关于该系统的论文(当时还没有称为VisuAlgo),以及此链接阅读2015年的简短更新(将VisuAlgo与之前的项目关联起来)。


错误报告或新功能请求

VisuAlgo并不是一个完成的项目。Steven Halim副教授仍在积极改进VisuAlgo。如果您在使用VisuAlgo时发现任何可视化页面/在线测验工具中的错误,或者您想要请求新功能,请联系Steven Halim副教授。他的联系方式是将他的名字连接起来,然后加上gmail dot com。

隐私政策

版本 1.2 (更新于2023年8月18日星期五)。

自2023年8月18日(星期五)起,我们不再使用 Google Analytics。因此,我们现在使用的所有 cookies 仅用于此网站的运营。即使是首次访问的用户,烦人的 cookie 同意弹窗现在也已关闭。

自2023年6月7日(星期五)起,由于 Optiver 的慷慨捐赠,全世界的任何人都可以自行创建一个 VisuAlgo 账户,以存储一些自定义设置(例如,布局模式,默认语言,播放速度等)。

此外,对于 NUS 学生,通过使用 VisuAlgo 账户(一个 NUS 官方电子邮件地址,课堂名册中的学生姓名,以及在服务器端加密的密码 - 不存储其他个人数据),您同意您的课程讲师跟踪您的电子讲义阅读和在线测验培训进度,这是顺利进行课程所必需的。您的 VisuAlgo 账户也将用于参加 NUS 官方的 VisuAlgo 在线测验,因此,将您的账户凭据传递给他人代您进行在线测验构成学术违规。课程结束后,您的用户账户将被清除,除非您选择保留您的账户(OPT-IN)。访问完整的 VisuAlgo 数据库(包含加密密码)的权限仅限于 Halim 教授本人。

对于全球其他已经给 Steven 写过信的 CS 讲师,需要一个 VisuAlgo 账户(您的(非 NUS)电子邮件地址,您可以使用任何显示名称,以及加密密码)来区分您的在线凭据与世界其他地方。您的账户将具有 CS 讲师特定的功能,即能够查看隐藏的幻灯片,这些幻灯片包含了在隐藏幻灯片之前的幻灯片中提出的问题的(有趣的)答案。您还可以访问 VisuAlgo 在线测验的 Hard 设置。您可以自由地使用这些材料来增强您的数据结构和算法课程。请注意,未来可能会有其他 CS 讲师特定的功能。

对于任何拥有 VisuAlgo 账户的人,如果您希望不再与 VisuAlgo 工具有关联,您可以自行删除您的账户。