# Dynamic Ring Exploration with \((H,s)\) View +
## 5 Upper Bound of Exploration Time for \(S\geq N-1\)  
In this section, we consider the upper bound of the exploration time when \(S\geq n-1\). We show that the upper bound of the exploration time is reduced to \(O(n^{2}/H+n\log H)\) in this case by giving an exploration algorithm. We first introduce a new operation \(\textsc{ExpHalf}(t,v_{i})\) that is used as a building block to construct the exploration algorithm. **ExpHalf. **\(\textsc{ExpHalf}(t,v_{i})\) described in Algorithm 4 is an algorithm by which \(A\) explores \(\lceil|\overline{V^{t}}|/2\rceil\) nodes when \(A\) starts \(\textsc{ExpHalf}(t,v_{i})\) from \(v_{i}\) at the \(t\)-th step under the assumption that \(v_{i}\) is the right or left extremity of \(V^{t}\), \(|\overline{V^{t}}|\leq 2H\), and \(S\geq n-1\). Note that in the following, when \(A\) executes \(\textsc{ExpHalf}(t,v_{i})\), \(A\) is always on the right or left extremity of \(V^{t}\). When starting the algorithm, \(A\) first sees if \(v_{i}\) is the right extremity or the left one and stores _right_ if \(v_{i}\) is the right extremity or otherwise _left_ in _dir_. If \(A\) can move \(\lceil|\overline{V^{t}}|/2\rceil\) hops to _dir_ by the \((t+n-1)\)-th step according to the view, \(A\) does so (Figure 3(b)). Otherwise, \(A\) moves \(n-|\overline{V^{t}}|/2\) hops to \(\overline{dir}\) (Figure 3(c)). ```
1:\(dir\leftarrow\text{\it Extremity}(t,v_{i})\)
2:if\(A\) can move \(\lceil\left|\overline{V^{t}}\right|/2\rceil\) hops to \(dir\) by the \((t+n-1)\)-th step then
3: Move \(\lceil\left|\overline{V^{t}}\right|/2\rceil\) hops to \(dir\)
4:else
5: Move \(n-\lceil\left|\overline{V^{t}}\right|/2\rceil\) hops to \(\overline{dir}\)
6:Wait until the \((t+n-1)\)-th step
```  
**Algorithm 4**\(\textsc{ExpHalf}(t,v_{i})\)  
**Lemma 4**: _Suppose that at the \(t\)-th step, \(A\) exists at the right or left extremity, say \(v_{i}\), of \(V^{t}\) and starts \(\textsc{ExpHalf}(t,v_{i})\). If \(\left|\overline{V^{t}}\right|\leq 2H\) and \(S\geq n-1\), \(A\) can explore at least \(\lceil\overline{V^{t}}/2\rceil\) nodes by the \(t^{\prime}\)-th step (the end of \(\textsc{ExpHalf}(t,v_{i})\)) and exists on the right or left extremity of \(V^{t^{\prime}}\) at the \(t^{\prime}\)-th step where \(t^{\prime}=t+n-1\)._  
Proof: Without loss of generality, we assume \(v_{i}\) is the right extremity of \(V^{t}\). Let \(m=\left|\overline{V^{t}}\right|\), \(E_{r}=\{e_{i}\), \(e_{i+1}\), \(\ldots\), \(e_{i+\lceil m/2\rceil-1}\), \(e_{i+\lceil m/2\rceil+1}\), \(e_{i+\lceil m/2\rceil+2}\), \(\ldots\), \(e_{i-1}\}\). Now, consider the move of \(A\). Since \(S\geq n-1\) and \(m\leq 2H\), \(A\) can see whether it can move \(\lceil m/2\rceil\) hops to right by the \((t+n-1)\)-th step or not. If \(A\) can move \(\lceil m/2\rceil\) hops, \(A\) moves \(\lceil m/2\rceil\) hops to right and thus the lemma holds. Otherwise, \(A\) can move at most \(\lceil m/2\rceil-1\) hops to right by the \((t+n-1)\)-th step, which means during the \(n-1\) steps, there exist at least \(n-1-(\lceil m/2\rceil-1)=n-\lceil m/2\rceil\) steps at each of which one of the links in \(E_{r}\) is missing. Since at most one link is missing at each step and \(E_{r}\cap E_{l}=\emptyset\), every link in \(E_{I}\) exists at each of the \(n-\lceil m/2\rceil\) steps. By this and \(|E_{I}|=n-\lceil m/2\rceil\), \(A\) succeeds to reach \(v_{i+\lceil m/2\rceil}\) by moving to left, which means at least \(\lceil m/2\rceil\) nodes are explored. **Exploration algorithm. ** Algorithm 5 describes the exploration algorithm. The algorithm repeats \(\textsc{ExpH}(t,v_{i})\) for \(\lfloor(n-H^{\prime})/H^{\prime}\rfloor\) times (lines 1-5) and \(\textsc{ExpHalF}(t,v_{i})\) for \(\lceil\log(n-H^{\prime}\lfloor(n-H^{\prime})/H^{\prime}\rfloor-1)\rceil\) times (lines 6-10). We call the part repeating \(\textsc{ExpH}(t,v_{i})\) (lines 1-5) _the first part_ and the part repeating \(\textsc{ExpHalF}(t,v_{i})\) _the second part_ (lines 6-10).