Time complexity & Space complexity#

When analyzing the time complexity, generally $T_{avg}(N)$ and $T_{worst}(N)$​ are analyzed.

1. $T(N)=O(f(N))$ if there are positive constants $c$ and $n_0$ such that $T(N)\leq c\times f(N)$ for all $N\geq n_0$ .

2. $T(N)=\Omega (g(N))$ if there are positive constants $c$ and $n_0$ such that $T(N)\geq c\times g(N)$ for all $N\geq n_0$ .

3. $T(N)=\Theta (h(N))$ if and only if $T(N)=O(h(N))$ and $T(N)=\Omega(h(N))$.

4. $T(N)=o(h(N))$ if $T(N)=O(p(N))$ and $T(N)\neq \Theta (p(N))$​.

Always pick the smallest upper bound and the largest lower bound.

• If $T_1(N)=O(f(N))$ and $T_2(N)=O(g(N))$, then:

  $T_1(N)+T_2(N)=\max(O(f(N)),O(g(N)))$

  $T_1(N)\times T_2(N)=O(f(N)\times g(N))$

• $\log^k N=O(N)$ for all constant $k$​ (Logarithms grow very slowly)

Example: Fibonacci number

int Fib(int N){
	if(N<=1){
		return 1;
	}else{
		return Fib(N-1)+Fib(N-2);
	}
}

$T(N)=T(N-1)+T(N-2)+2$

$(\frac{3}{2})^N \leq Fib(N) \leq (\frac{5}{3})^N$​

When $T(N)=O(f(N))$, it is guaranteed that $\lim\limits_{N\to\infty} \frac{f(N)}{T(N)} = constant$ or $\lim\limits_{N\to\infty}\frac{f(N)}{T(N)}=+\infty$​

Max Subsequence Sum#

• Problem Description: Given (possibly negative) integers $A_1, A_2, \cdots, A_N$, find the maximum value of $\sum\limits_{k=i}^{j} A_k$.

• Algorithm 1

  int MaxSubsequenceSum(int A[],int N){
  	int ThisSum,MaxSum,i,j,k;
      MaxSum=0;
      for(i=0;i<N;i++){
          for(j=i;j<N;j++){
              ThisSum=0;
              for(k=i;k<=j;k++){
                  ThisSum+=A[k];
              }
              if(ThisSum>MaxSum){
                  MaxSum=ThisSum;
              }
          }
      }
      return MaxSum;
  }

  This algorithm is simple and easy to understand: Find all the possible subsequences and compare them to find the maximum value.

  Nevertheless, it is a typically bad algorithm with $T(N)=O(N^3)$​​.

• Algorithm 2

  int MaxSubsequenceSum(int A[],int N){
      int ThisSum,MaxSum,i,j;
      MaxSum=0;
      for(i=0;i<N;i++){
          ThisSum=0;
          for(j=i;j<N;j++){
              ThisSum+=A[j];
              if(ThisSum>MaxSum){
                  MaxSum=ThisSum;
              }
          }
      }
      return MaxSum;
  }

  The idea of this algorithm is basically simple to the previous one. However, is does an improvement because it scans through all the subsequences in a smarter way and reduce time complexity to $O(N^2)$.

• Algorithm 3 Divide and Conquer

  int MaxSubSum(int A[],int left,int right){
      int MaxLeftSum,MaxRightSum;
      int MaxLeftBorderSum,MaxRightBorderSum;
      int LeftBorderSum,RightBorderSum;
      int center,i;
      
      if(left==right){
          if(A[left]>0){
              return A[left];
          }else{
              return 0;
          }
      }
      
      center=(left+right)/2;
      MaxLeftSum=MaxSubSum(A,left,center);
      MaxRightSum=MaxSubSum(A,center+1,right);
      
      MaxLeftBorderSum=0;
      LeftBorderSum=0;
      for(i=center;i>=left;i--){
          LeftBorderSum+=A[i];
          if(LeftBorderSum>MaxLeftBorderSum){
              MaxLeftBorderSum=LeftBorderSum;
          }
      }
      
      MaxRightBorderSum=0;
      RightBorderSum=0;
      for(i=center+1;i<=right;i++){
          RightBorderSum+=A[i];
          if(RightBorderSum>MaxRightBorderSum){
              MaxRightBorderSum=RightBorderSum;
          }
      }
      
      return MaxThree(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);
  }
  
  int MaxSubsequenceSum(int A[],int N){
      return MaxSubSum(A,0,N-1);
  }

  A complicated algorithm which involves recursions. The idea of the algorithm is to divide the whole set into two equal parts, calculate the max length of left part and right part, calculate the max length of subsequence which begins from center and extend leftward and rightward and return the maximum value of the three as the result.

  Time complexity analysis:

  $T(N)=2T(\frac{N}{2})+N$

  $T(N)=O(N\log N)$

  which is much better than $O(N^3)$ and $O(N^2)$.

• Algorithm 4 Online Algorithm

  int MaxSubSequenceSum(int A[],int N){
      int ThisSum,MaxSum,j;
      ThisSum=0;
      MaxSum=0;
      for(j=0;j<N;j++){
          ThisSum+=A[j];
          if(ThisSum>MaxSum){
              MaxSum=ThisSum;
          }
          if(ThisSum<0){
              ThisSum=0;
          }
      }
      return MaxSum;
  }

  As is shown above, the algorithm is an online algorithm, which means that it can always return the correct result currently whenever it stops.

  The idea of the algorithm is easy to understand. It simply scans through the whole array, add each value to $ThisSum$ and update it if necessary. If $ThisSum<0$​, it is set 0 because we can exclude the negative part in the max subsequence.

  The time complexity of this algorithm is $O(N)$​​, the best algorithm of all.

Binary Search#

• Problem Description: Given a sorted array $A$ and its size $N$, we need to find a particular element $X$. If found, return the index, otherwise return $-1$.

• Algorithm

  int BinarySearch(int A[],int N,int X){
      int Low,Mid,High;
      Low=0;
      High=N-1;
      while(Low<=High){
          Mid=(Low+High)/2;
          if(A[Mid]==X){
              return Mid;
          }else if(A[Mid]<X){
              Low=Mid+1;
          }else{
              High=Mid-1;
          }
      }
      return -1;
  }

  Time complexity analysis:

  $T(N)=T(\frac{N}{2})+C$

  $T(N)=O(\log N)$

Applications#

void PrintList(List L){
    if(L!=NULL){
        printf("%d",L->Element);
        PrintList(L->Next);
    }
}

void PrintList(List L){
top:if(L!=NULL){
        printf("%d",L->Element);
        L=L->Next;
        goto top;
    }
}

Expression Tree#

An expression tree is composed of operators and operands, where operands are leaf nodes and the calculation of the expression can be conducted from bottom to top.

• Problem Description: Given an infix/postfix expression, constructing an expression tree.

• Algorithm (In Pseudocode)

  Transform the expression to POSTFIX expression
  Create a Stack
  	Scan through the postfix expression:
  		if Current is Operand:
  			Push(Current,Stack)
  		else:
  			Get two elements from Stack, temp1 and temp2
  			Construct a tree:
  				Current as the root, temp1 and temp2 be left and right subtrees
  			Push the tree into Stack
  return Stack[0]

Tree Traversals#

Preorder Traversal, Inorder Traversal, Postorder Traversal and Levelorder Traversal

void Preorder(Tree_ptr Tree){
    visit(Tree);
    Preorder(Tree->Left);
    Preorder(Tree->Right);
}

void Postorder(Tree_ptr Tree){
    Postorder(Tree->Left);
    Postorder(Tree->Right);
    visit(Tree);
}

void Levelorder(Tree_ptr Tree){
    Queue Q;
    Enqueue(Tree);
    while(Q is not empty){
        visit(Q[Front]);
        Dequeue(Q);
        for(Each child C of Q[Front]){
            Enqueue(C);
        }
    }
}

Threaded Binary Tree#

Take the Inorder threaded binary tree as an example:

If $Tree->Left$ is NULL, replace it with a pointer to the inorder predecessor of the Tree. If $Tree->Right$ is NULL, replace it with a pointer to the inorder successor of the Tree.

There must bot be ant loose threads. Therefore a head node is needed such that the left pointer of the first item in traversal and the right pointer of the last item in traversal point to it.

typedef struct ThreadedTreeNode* PtrToThreadedNode;
struct ThreadedTreeNode{
    bool LeftThread;
    PtrToThreadedNode LeftPtr;
    ElementType Element;
    bool RightThread;
    PtrToThreadedNode RightPtr;
};

• Some Terminologies:

  Skewed Binary Tree: Trees that degenerate to linked list

  Complete Binary Tree: All the leaf nodes are on two adjacent levels. On the last level, leaf nodes always begin from left.

  Full Binary Tree: Each node excluding leaf node has exactly $m$ children.

  Perfect Binary Tree: A tree of height $h$ has $2^{h+1}-1$ nodes.

Properties of Binary Tree#

1. For trees with $N$ nodes, they have $N-1$ edges.

2. The maximum number of nodes on level $i$ is $2^i$​. The maximum number of nodes in a binary tree of depth $k$ is $2^{k+1}-1$.

3. Let $n_i$ denotes a node of degree $i$, we have: $n_0=n_2+1$.

   Prove: $n=n_0+n_1+n_2$ , $E=n-1=n_0+n_1+n_2-1=n_1+2n_2$ $\therefore n_0=n_2+1$​

An Important Problem#

Given a preorder traversal sequence and an inorder traversal sequence, build a binary from those two arrays. (Similarly we can define a problem whose input is the inorder and postorder traversal sequences and output is a binary tree.)

Here is a problem on LeetCode:

Structure and function interface:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize);

Solution:

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if(preorderSize==0){
        return NULL;
    }
    struct TreeNode* T=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    int root=preorder[0];
    int i;
    for(i=0;i<inorderSize;i++){
        if(inorder[i]==root){
            break;
        }
    }
    T->val=root;
    T->left=buildTree(preorder+1,i,inorder,i);
    T->right=buildTree(preorder+1+i,preorderSize-1-i,inorder+i+1,inorderSize-1-i);
    return T;
}

The idea is simple, while the implementation is a little bit complicated. Given the preorder traversal sequentially visit the root node, the left subtree and the right subtree, we know that the first element in preorder traversal is the root of the current tree. Then we find the root node in the inorder traversal. Because the inorder traversal visits the left subtree, the current node and the right subtree sequentially, we can divide the inorder traversal sequence into 3 parts: Left subtree, current node and right subtree, while the current node is the first element in preorder sequence. Then we recursively conduct the procedure and eventually build a corresponding binary tree.

Search Tree ADT#

A binary search tree is a binary tree with distinct integers as its keys.

The keys in the left subtree are smaller than root node, while the keys in the right subtree are larger than root node. Such property makes searching and finding easier.

• Key Operations:

  1. Find a particular element in BST
  2. Insert a new element into BST
  3. Delete a certain element in BST

• Find

  Recursive:

  Tree_ptr Find(ELementType X,Tree_ptr T){
      if(T==NULL){
          return NULL;
      }
      if(T->Element==X){
          return T;
      }else if(T->Element<X){
          Find(X,T->Right);
      }else{
          Find(X,T->Left);
      }
  }

  Iterative:

  Tree_ptr Find(ELementType X,Tree_ptr T){
      while(T!=NULL){
          if(T->Element==X){
              return T;
          }else if(T->Element>X){
              T=T->Left;
          }else{
              T=T->Right;
          }
      }
      return NULL;
  }

  $T(N)=O(Depth)=O(\log N)(Best\ Case)=O(N)(Worst\ Case)$

FindMin and FindMax are basically simple and identical: For FindMin: Keep going leftward and return the value of the terminal node.

• Insert

  Tree_ptr Insert(ElementType X,Tree_ptr T){
      if(T==NULL){
          T=(Tree_ptr)malloc(sizeof(struct TreeNode));
          T->Element=X;
          T->Left=NULL;
          T->Right=NULL;
      }
      if(T->Element>X){
          T->Left=Insert(X,T->Left);
      }else if(T->Element<X){
          T->Right=Insert(X,T->Right);
      }
      return T;
  }

  $T(N)=O(Depth)=O(\log N)(Best\ Case)=O(N)(Worst\ Case)$

• Delete

  There are 3 cases in total:

  1. Deleting a leaf node: Simply set the pointer of its parent node to NULL.

  2. Deleting a node of degree 1: Replace the node by its child.

  3. Deleting a node of degree 2:

     Picking the largest element in left subtree or the smallest element in right subtree and replace the current node with picked one.

     Deleting the node from the subtree. ($Degree=0\ or\ 1$​)

     That is, we transform the problem to delete a node of degree 0 or 1.

  Tree_ptr Delete(ElementType X,Tree_ptr T){
      if(X>T->Element){
          T->Right=Delete(X,T->Right);
      }else if(X<T->Element){
          T->Left=Delete(X,T->Left);
      }else{
          if(T->Left==NULL&&T->Right==NULL){
              return NULL;
          }else if(T->Left==NULL){
              return T->Right;
          }else if(T->Right==NULL){
              return T->Left;
          }else{
              TmpCell=FindMin(T->Right);    /*Or FindMax(T->Left)*/
              T->Element=TmpCell->Element;
              T->Right=Delete(T->Element,T->Right);
              return T;
          }
      }
  }

  $T(N)=O(Depth)=O(\log N)(Best\ Case)=O(N)(Worst\ Case)$

  Lazy Deletion: Does not actually delete an node. Instead, add a mark to each node that determines whether the node is legitimate or empty. Lazy deletions can significantly improve the efficiency of operations.

Binary Heap#

A binary tree with $n$ nodes and height $h$ is complete iff its nodes correspond to the nodes numbered from $1$ to $n$ in the perfect binary tree of height $h$.

A binary heap is a complete binary tree.

When using array implementation, $H[0]$​ will not be used, elements begin from index 1.

void Insert(Heap H,int X){
    H->Size++;
    H->Elements[H->Size]=X;
    PercolateUp(H->Elements,H->Size);
}

int DeleteMin(Heap H){
    int temp=H->Elements[1];
    H->Elements[1]=H->Elements[H->Size];
    H->Size--;
    PercolateDown(H->Elements,H->Size,1);
    return temp;
}

void BuildHeap(int A[],int N){
    int i;
    for(i=0;i<N;i++){
        Heap[i+1]=A[i];
    }
    for(i=N/2;i>0;i--){
        PercolateDown(Heap,N,i);
    }
}

$d-$ Heap#

A $d-$heap is a heap whose nodes have $d$ children.

DeleteMin will take $d-1$ comparisons to find the smallest child. Hence the total time complexity would be $O(d\log_d N)$​.

Relation#

A relation $R$ is defined on a set $S$ if for every pair of elements $(a,b)$, $a,b\in S$, $a\ R\ b$ is either true or false. If $a\ R\ b$ is true, then we say that $a$ is related to $b$.

A relation, $\sim$, over a set, $S$, is said to be an equivalence relation over $S$ if and only if it is symmetric, reflexive and transitive over $S$. If $x$ and $y$ are in the same equivalence class, then $x\sim y$​.

Operations#

[Example] $S_1=\{6,7,8,10\}, S_2=\{1,4,9\},S_3=\{2,3,5\}$

Note that all the sets are disjoint ($S_i\cap S_j=\empty$).

In the array representation, $A[7]=6,A[8]=6,A[10]=6,A[6]=-4,etc$.

Common operations:

$Union(i,j)::=$ Replace $S_i$ and $S_j$ by $S=S_i\cup S_j$.

$Find(i)::=$ Find the set $S_k$ which contains the element $i$ and return the index of the root.

void Union(int set[],int num1,int num2){
    int root1,root2;
    root1=Find(Set,num1);
    root2=Find(Set,num2);
    if(root1==root2){
        return;
    }
    set[root2]=root1;
}

void Union(int set[],int num1,int num2){
    int root1,root2;
    root1=Find(Set,num1);
    root2=Find(Set,num2);
    if(root1==root2){
        return;
    }
    if(set[root1]<set[root2]){
        set[root1]=set[root1]+set[root2];
        set[root2]=root1;
    }else{
        set[root2]=set[root1]+set[root2];
        set[root1]=root2;
    }
}

void Union(int set[],int rank[],int num1,int num2){
    int root1=Find(set,num1);
    int root2=Find(set,num2); 
    if(root1==root2){
        return;
    }  
    if(rank[root1]<rank[root2]){
        set[root1]=root2;
    }else if(rank[root1]>rank[root2]){
        set[root2]=root1;
    }else{
        set[root1]=root2;
        rank[root2]++;
    }
}

int Find(int set[],int num){
    while(set[num]>0){
        num=set[num];
    }
    return num;
}

int Find(int set[],int num){
    int root,current,parent;
    root=num;
    while(root>0){
        root=set[root];
    }
    current=num;
    while(current!=root){
        parent=set[current];
        set[current]=root;
        current=parent;
    }
    return root;
}

Definitions and terminologies#

Self loop and Multigraph are not considered.

Representation of Graph#

Topological Sort#

[Example] Courses with prerequisites need to be arranged in a university. As an illustration, “Programming 1” and “Discrete Mathematics” are required before learning “Data Structure”, so a student is supposed to take the two courses in semester 1 and “Data Structure” in semester 2.

Topological sort is based on an AOV (Activity on Vertex) Network, with vertices representing activities (courses) and edges representing precedence relations.

An topological order (not unique) is a linear ordering of vertices of a graph such that for any two vertices $i,j$, if $i$ is a predecessor of $j$ in the network then $i$ precedes $j$ in the linear ordering.

Implementation:

void Topsort(Graph G){
    Queue Q;
    int count=0;
    Vertex V,W;
    for(each vertex V){
        if(Indegree[V]==0){
            Enqueue(V,Q);
        }
    }
    while(Q is not empty){
        V=Dequeue(Q);
        TopNum[V]=count;
        count++;
        for(All the adjacent vertices W of V){
            if(--Indegree[W]==0){
                Enqueue(W,Q);
            }
        }
    }
    if(count!=NumberOfVertex){
        Error("Graph has a cycle");
    }
}

The data structure used in the algorithm is a queue, which stores the vertices of degree 0. When a vertex is dequeued and marked, the indegree of all the adjacent vertices will -1.

Time complexity equals to $O(V+E)$.

Unweighted Shortest Path (BFS)#

As shown in the title, the idea is Breadth-First-Search (BFS), which means we begin from a particular vertex and scan through the graph level by level.

void BFS(Graph G,Vertex S){
    Queue Q;
    Vertex V,W;
    Enqueue(S,Q);
    distance[S]=0;
    while(Q is not empty){
        V=Dequeue(Q);
        for(All the adjacent vertices W of V){
            if(distance[W]==Infinity){
                distance[W]=distance[V]+1;
                Enqueue(W,Q);
            }
        }
    }
}

The algorithm is quite similar to topological sort. Both need a queue as a container and involves a procedure of checking a vertex’s adjacent vertices. Time complexity equals to $O(V+E)$.

Weighted Shortest Path (Dijkstra’s Algorithm)#

Dijkstra’s algorithm cannot handle graphs with negative cost edge.

Three arrays need to be maintained in Dijkstra’s algorithm: $Known[\ ],\ Distance[\ ]\ and\ Path[\ ]$​.

Here is the implementation of the algorithm:

void Dijkstra(Graph G,Vertex S){
    for(i=0;i<NumV;i++){
        Known[i]=0;
        Distance[i]=Infinity;
        Path[i]=0;
    }
    Known[S]=1;
    Distance[S]=0;
    while(1){
        V=unknown vertex with smallest distance;
        Known[V]=1;
        for(i=0;i<NumV;i++){
            if(G[V][i]!=0&&Known[i]==0&&Distance[V]+G[V][i]<Distance[i]){
                Distance[i]=Distance[V]+G[V][i];
                Path[i]=V;
            }
        }
    }
}

We can divide the algorithm into 4 steps:

1. Find the unknown vertex with smallest distance.
2. Mark the vertex as “Known”.
3. Find the vertex’s all the adjacent vertices that have not been visited.
4. Compare the original distance and new distance, update it if necessary.

For step 1, to find the vertex with smallest distance, there are 2 implementations:

• Simply scan the graph: $O(V)$, overall time complexity $O(V^2+E)$.
• Keep distances in a heap and call DeleteMin: $O(\log V)$. Considering the adjustment of the heap after conducting $Distance[i]=Distance[V]+G[V][i]$, the overall time complexity equals to $O(V\log V+E\log V)=O(E\log V)$​.

Graph with Negative Edge Cost#

A special type of graph. Negative edge cost means that Dijkstra’s algorithm can no longer be used, instead we keep a queue as the container and visit each edge $\geq$ 1 time ($Known[\ ]$ is meaningless).

void Negative(Graph G,Vertex S){
    Queue Q;
    Vertex V,W;
    Enqueue(S,Q);
    Inqueue[S]=1;
    while(Q is not empty){
        V=Dequeue(Q);
        Inqueue[V]=0;
        for(All the adjacent vertices W of V){
            if(distance[V]+G[V][W]<distance[W]){
                distance[w]=distance[V]+G[V][W];
                if(Inqueue[W]==0){
                    Enqueue(W,Q);
                    Inqueue[W]=1;
                }
            }
        }
    }
}

AOE (Activity on Edge) Network#

AOE network imitates the process of scheduling a project. We will discuss the Earliest Completion time (EC), Latest Completion time (LC) and Critical Path Method (CPM).

• Calculation of EC: Start from $V_0$, for any $a_i=<v,w>$, we have $EC[w]=\max\{EC[v]+Cost_{<v,w>}\}$.
• Calculation of LC: Start from last vertex, for any $a_i=<v,w>$, we have $LC[v]=\min\{LC[w]-Cost_{<v,w>}\}$.
• Slack time of $<v,w>=LC[w]-EC[v]-Cost_{<v,w>}$.
• Critical Path ::= the path consisting entirely of zero-slack edges.

Network Flow Problem#

Given a network of pipes, we need to determine the maximum amount of flow that can pass from $s(source)$ to $t(sink)$​.

$G$ is the original graph, Flow $G_f$ is the graph represents the result, while $G_r$ is the graph that shows the remaining flow.

Minimum Spanning Tree#

A spanning tree of a graph $G$ is a tree which consists of $V(G)$ and a subset of $E(G)$.

• Minimum: the sum of weight of all edges is minimized.
• Tree: acyclic, $E=V-1$.
• Spanning: the tree contains every vertex in the original graph.

There are two algorithms to find the minimum spanning tree, Prim’s Algorithm and Kruskal’s Algorithm. Both are greedy algorithms because the find the edge with minimum weight at each step.

Tree Prim(Graph G){
    Tree={};
    Find the edge(V,W) with smallest weight;
    Add vertex V,W and edge(V,W) to the tree;
    for(i=1;i<=NumV-2;i++){
        Find the minimum cost edge(X,Y) deriving from the vertices of the current tree that does not form a cycle;
        Add vertex Y and edge(X,Y) to the tree;
    }
    return Tree;
}

Tree Kruskal(Graph G){
    Tree={};
    for(i=1;i<=NumV-1;i++){
        Find a minimum cost edge(V,W) in G that does not from a cycle after added to Tree;
        Add V,W(if necessary) and edge(V,W) to the tree;
    }
    return Tree;
}

Depth First Search (DFS)#

Depth First Search is a traversal of all vertices that makes depth its priority. We search deeper and deeper until we cannot go further. Then we return to the previous vertices (retrospect) and recursively conduct the procedure.

void DFS(Graph G,Vertex S){
    visited[S]=true;
    print(S);
    for(All the adjacent vertices W of S){
        if(visited[W]==false){
            DFS(G,W);
        }
    }
}

The algorithm is simple and easy to understand. We can regard this algorithm as a generalization of preorder traversal. Recursions are used to conduct DFS.

There is a lot of applications of DFS, here I list two important ones: Biconnectivity and Euler Circuit.

void StronglyConnectedComponents( Graph G, void (*visit)(Vertex V) ){
    int i;
    for(i=0;i<G->NumOfVertices;i++){
        if(dfn[i]==0){
            tarjan(G,i);
        }
    }
}

void tarjan(Graph G,int vertex){
    int temp;
    
    stack[++ptr]=vertex;
    instack[vertex]=1;
    dfn[vertex]=time;
    low[vertex]=time;
    time++;

    PtrToVNode pointer=G->Array[vertex];
    while(pointer!=NULL){
        temp=pointer->Vert;
        if(dfn[temp]==0){
            tarjan(G,temp);
            if(low[temp]<low[vertex]){
                low[vertex]=low[temp];
            }
        }else if(instack[temp]==1){
            if(dfn[temp]<low[vertex]){
                low[vertex]=dfn[temp];
            }
        }
        pointer=pointer->Next;
    }
    if(dfn[vertex]==low[vertex]){
        int top;
        do{
            top=stack[ptr];
            printf("%d ",top);
            instack[top]=0;
            ptr--;
        }while(top!=vertex);
        printf("\n");
    }
}

Insertion Sort#

void Insertion_Sort(int A[],int N){
    int i,j,temp;
    for(i=1;i<N;i++){
        temp=A[i];
        for(j=i;j>0&&A[j-1]>temp;j--){
            A[j]=A[j-1];
        }
        A[j]=temp;
    }
}

The algorithm is simple. We can use an analogy to describe it: Assume that you are playing cards. When you have a coming card, you need to insert the new card into your cards. So you just keep searching backward until you find a card whose value is smaller than the new card. Then it is the proper position to conduct insertion.

Time complexity analysis:

• Worst case (reversed order): $T(N)=O(N^2)$.
• Best case (sorted order): $T(N)=O(N)$.

An inversion in an array is any ordered pair $(i,j)$ such that $i<j$ but $A[i]>A[j]$.

Each swap of adjacent elements eliminates exactly 1 inversion. Thus $T(N)=O(Inversions+N)$.