การเรียงลำดับจุดทั้งหมดมีความซับซ้อนด้านเวลาเป็น O(n log n) ส่วนการทำงานในวงวนตรวจสอบว่าการเลือกจุดถัดไปเป็นการ "เลี้ยวขวา" หรือ "เลี้ยวซ้าย" ใช้เวลาเพียง O(n) เนื่องจากจุดใดๆจะนำมาตรวจสอบเพียงสองครั้ง หากตรวจสอบแล้วพบว่าเป็นจุด ( x 2 , y 2 ) {\displaystyle (x_{2},y_{2})} ในการ "เลี้ยวซ้าย" ขั้นตอนวิธีจะดำเนินต่อไปยังจุด ( x 3 , y 3 ) {\displaystyle (x_{3},y_{3})} และถ้าหากพบว่าเป็นจุด ( x 2 , y 2 ) {\displaystyle (x_{2},y_{2})} ในการเลี้ยวขวา จุดนั้นก็จะไม่ถูกนำมาพิจารณาอีก ดังนั้น เกรแฮมสแกน มีความซับซ้อนทางเวลาเป็น O(n log n) ตามการเรียงลำดับจุด ซึ่งใช้เวลามากที่สุดในขั้นตอนวิธี