The Gateway to Computer Science Excellence
0 votes
14 views
Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?
in Algorithms by Boss (41.9k points) | 14 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 Active (1.3k points)

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
50,648 questions
56,429 answers
195,207 comments
99,917 users