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

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

ซึ่งข้อพิสูจน์ดังกล่าวจะเป็นจริงก็ต่อเมื่อเอสตาร์สอดคล้องกับเงื่อนไขต่อไปนี้

• เอสตาร์ใช้ฮิวริสติกที่ยอมรับได้ ไม่เช่นนั้นจะไม่สามารถรับประกันได้ว่าเอสตาร์จะค้นหาโดยใช้จำนวนโหนดน้อยกว่าขั้นตอนวิธีที่มีฮิวริสติกเดียวกัน[3]
• เอสตาร์แก้ปัญหาการค้นหาเพียงปัญหาเดียว ไม่ได้ใช้แก้ปัญหาการค้นหาที่คล้าย ๆ กันหลายปัญหา ไม่เช่นนั้นจะไม่สามารถรับประกันได้ว่าเอสตาร์จะค้นหาโดยใช้จำนวนโหนดน้อยกว่าขั้นตอนวิธีที่มีฮิวริสติกที่มีส่วนเพิ่มขึ้นมา[4]