# A Fast Algorithm for Three-Way Object-Oriented Concept Acquisition
## 4 Algorithm Description and Time Complexity
### Time Complexity  
The time complexity of Algorithm 1 is analyzed as follows: According to Equations (2) and (4), executing Steps 2-3 takes \(\mathcal{O}(2|U|\times|V|)\) to obtain all single-attribute concepts (Definition 2) from the formal context \((U,V,R)\) and its complement context \((U,V,R^{c})\). According to Definition 3 and Proposition 8, the time complexity of function \(\lambda\) is \(\mathcal{O}(|U|+|C_{a}|+|C_{a}^{c}|)\), and it is \(\mathcal{O}(|U|+2|V|)\) in the worst case. Thus, Steps 4-5 take at most \(\mathcal{O}(2|U|\times|V|+4|V|^{2})\) to obtain all basic OEO concepts, \(B_{OEO}\) (Definition 4). Steps 6-16 take at most \(\mathcal{O}(\sum\limits_{k=2}^{|U|}(|C_{OEO}^{k-1}|\times\sum\limits_{j=1}^{k -1}|C_{OEO}^{j}|)\times(|U|+2|V|))\). Based on Equation (20), letting \(|OEOL(U,V,R)|=\sum\limits_{k=0}^{|U|}(|C_{OEO}^{k}|)\), we can obtain the total time complexity of Algorithm 1 as \(\mathcal{O}(4|U|\times|V|+4|V|^{2}+(|U|+2|V|)\times|OEOL(U,V,R)|^{2})\). As \(|OEOL(U,V,R)|\) is significantly larger than \(|V|\), the time complexity of Algorithm 1 is \(\mathcal{O}((|U|+2|V|)\times|OEOL(U,V,R)|^{2})\). Example 2 illustrates the process of constructing OEO-concepts for the 3 WOC algorithm. The details are as follows:  
**Example 2**. : _The formal context \((U_{1},V_{1},R_{1})\) is shown in Table 1 while the complement context is shown in Table 2. The object set is \(U_{1}=1\), \(2\), \(3\), \(4\), \(5\) and the attribute set is \(V_{1}=a\), \(b\), \(c\), \(d\), \(e\). For the sake of clarity, the extents of the concepts considered in this example are still represented in the form of object sets. Additionally, the hash key of the extent of each concept is also provided._  
_By using \(g\) and \(g\) (Equations (2) and (4)), we can obtain sets of single-attribute concepts \(C_{s}\) and \(C_{s}^{c}\) (Definition 2), as shown in Table 3. The hash key can be obtained by using the above function \(h\) (Definition 10) on the extent of each concept. For instance, the object set [1,2,4,5] is the extent of the single-attribute concept \((1245,a)\). Thus, its hash key is \(h(\{1,2,4,5\})=2^{0}+2^{1}+2^{3}+2^{4}=27\)._  
_According to line 1 in Algorithm 1, \(C_{OEO}^{0}\) is \([key:0,(\mathcal{O},(\mathcal{O},\mathcal{O}))]\). Based on Proposition 3, all 1-granularity OEO-concepts have been constructed. In this example, \(C_{OEO}^{1}\) = \(\{[key:1,(1,(d,\varnothing))],[key:4,(3,(\varnothing,a))]\}\). In order to obtain all 2-granularity OEO-concepts except for \(B_{OEO}^{2}\), we need to perform \(M(c_{1},c_{2})\), such that \(\forall c_{1}\in C_{OEO}^{1}\) and \(\forall c_{2}\in C_{OEO}^{0}\cup C_{OEO}^{1}\). Thus, key: 1 OR key: 4 = key: \(5=h(\{1\}\cup\{3\})\) based on Proposition 8. Thus we get \(C_{\mathcal{C}anti}^  
_We now construct \(C^{3}_{OEO}\), i.e., \(k=3\). \(\forall c_{1}\in C^{2}_{OEO}\) and \(\forall c_{2}\in C^{1}_{OEO}\cup C^{2}_{OEO}\), \(M(c_{1},c_{2})\) are computed. This yields the following candidate OEO-concepts: \([key:11,(124,(d,e))]\), \([key:7,(123,(cd,a))]\), \([key:21,(135,(bd,a))]\), \([key:14,(234,(\emptyset,ae))]\), \([key:23,(1235,(bcd,a))]\), \([key:30,(2345,(b,ae))]\), and \([key:15,(1234,(d,ae))]\). Similarly, we can obtain \([key:7,(123,(cd,a))]\) and \([key:14,(234,(\emptyset,ae))]\) as new OEO-concepts according to Proposition 6, and we add them to \(C^{3}_{OEO}\): \([key:23,(1235,(bcd,a))]\), \([key:30,(2345,(b,ae))]\), and \([key:15,(1234,(d,ae))]\) are 4-granularity candidate OEO-concepts now. We can obtain \(C^{4}_{OEO}\) when \(k=4\). Finally, all OEO-concepts are obtained as shown in Table 6._  
_Furthermore, the three-way object-oriented concept lattice \((OEOL(U_{1},V_{1},R_{1}),\leq)\) can be built based on the partial relationship between the concepts (Equation (14)). The lattice is shown in Figure 1, in which the concepts marked with a box are basic OEO-concepts._  
_For any two formal contexts, \((U,V,R)\) and \((U,T,J)\), \(V\) is the set of condition attributes, \(T\) is the set of decision attributes, and \(V\cap T=\emptyset\).