কমপ্লেক্সিটিঃ প্রায়োরিটি কিউতে পুশ করতে লগারিদম টাইম লাগে। এখানে প্রতিটা নোড একবার করে পুশ হবে, যেহেতু আমরা কোন নোড পুশ করার আগে দেখে নিচ্ছি সেটা আগেই ভিজিট করা হয়েছে কিনা। সুতরাং, এজ সংখ্যা |E| ও নোড সংখ্যা |V| হলে প্রিমসের টাইম কমপ্লেক্সিটি O((|V| + |E|) log |V|) = O(|E| log |V|)