Forksningsgruppa for algoritmeanalyse og kompleksitetsteori forskar på utvikling av framgangsmåtar (algoritmer) som løyser problem raskast mogleg på ein datamaskin. Fundamentale aspekt ved algoritmer blir studert, blant anna det viktige samspelet mellom datastrukturar og algoritmer. Ein stor del av arbeidet består i å analysere og samanlikne ulike algoritmer for å kunne forutseie kven som vil løyse eit gitt problem raskast. Det foregår også forsking med å lage tilnærmingsløysingar for problem som er så vanskelege at dei sannsynlegvis ikkje lar seg løyse innanfor rimelig tid. Fleire av problemstillingane som er aktuelle rettar seg mot bruk av parallelle datamaskinar.