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

| h ( x ) − h ∗ ( x ) | = O ( log ⁡ h ∗ ( x ) ) {\displaystyle |h(x)-h^{*}(x)|=O(\log h^{*}(x))}

h ∗ {\displaystyle h^{*}} คือฮิวริสติกที่เป็นคำตอบซึ่งเป็นค่าจาก x {\displaystyle x} ไปถึงเป้าหมาย และค่าความผิดพลาดของ h จะโตช้ากว่าหรือเท่ากับค่าลอการิทึมของ ฮิวริสติกที่สมบูรณ์ h ∗ {\displaystyle h^{*}} ที่ซึ่ง h ∗ {\displaystyle h^{*}} จะเป็นค่าความยาวของ x {\displaystyle x} ถึงเป้าหมาย[5][6]เปรียบเทียบระหว่าง ขั้นตอนวิธีของเดสตาร์กับขั้นตอนวิธีเอสตาร์