Most authors measure the time required to generate an explanans for a fixed input, model, and dataset, on specified hardware [Ross et al. (2017), Ribeiro et al. (2018), Zhang et al. (2018c), Cheng et al. (2019), Fusco et al. (2019), Ignatiev et al. (2019), Shakerin and Gupta (2019), Guo et al. (2020), Marques-Silva et al. (2020), Rajapaksha et al. (2020), Ramon et al. (2020), Warnecke et al. (2020), Bajaj et al. (2021), Faber et al. (2021), Lin et al. (2021), Malik et al. (2021), Pawelczyk et al. (2021), Rasouli and Yu (2021), Looveren and Klaise (2021), Wang et al. (2021), Amoukou et al. (2022), Belaid et al. (2022), Ma et al. (2022), Mercier et al. (2022), Vermeire et al. (2022), Bayrak and Bach (2023b), Brandt et al. (2023), Jin et al. (2023), Verma et al. (2024)].
In addition to empirical runtime, some authors analyze algorithmic complexity using $\mathcal{O}$-notation to characterize the worst-case or average-case number of steps required to run an explanation [Slack et al. (2019), Topin and Veloso (2019), Albini et al. (2020), Abrate and Bonchi (2021), Malik et al. (2021), Looveren and Klaise (2021)]. [Chen et al. (2019b)] further evaluate parallelizability to understand potential runtime improvements through hardware acceleration or distributed computation.