ประสิทธิภาพการทำงานในการหาส่วนประกอบที่เชื่อมกันแบบเข้มในกราฟที่เชื่อมกันแบบเข้มนั้น จะขึ้นอยู่กับว่าจะใช้ขั้นตอนวิธีแบบใดในการหาดังนี้

- ขั้นตอนวิธีของโกสรชุ จะมีประสิทธิภาพเป็น Θ ( V + E ) {\displaystyle \Theta (V+E)} เมื่อ V {\displaystyle V} แทนจำนวนจุดยอด และ E {\displaystyle E} แทนจำนวนเส้นเชื่อม

- ขั้นตอนวิธีของทาร์จัน จะมีประสิทธิภาพเป็น O ( V + E ) {\displaystyle O(V+E)} เมื่อ V {\displaystyle V} แทนจำนวนจุดยอด และ E {\displaystyle E} แทนจำนวนเส้นเชื่อม