Table of Contents Complexity analysisComplexity of edit distance Complexity of affine cost alignment Comparison Implementation efficiencyBand doubling for affine scores was never implemented WFA vs band doubling for affine costs ConclusionFuture work This note explores the complexity and performance of band doubling (Edlib) and WFA under varying cost models. Edlib (Šošić and Šikić 2017) uses band doubling and runs in \(O(ns)\) time, for sequence length \(n\) and edit distance \(s\) betwe...
