The Gateway to Computer Science Excellence
0 votes
26 views
Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?
in Algorithms by | 26 views

1 Answer

0 votes
We analyze the expected run time because it represents the more typical
time cost. Also, we are doing the expected run time over the possible random-
ness used during computation because it can’t be produced adversatively, unlike
when doing expected run time over all possible inputs to the algorithm.
by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,517 answers
201,937 comments
95,367 users