Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.13249 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911110434652160 |
|---|---|
| author | Kavun, Sergii |
| author_facet | Kavun, Sergii |
| contents | Traditional algorithm analysis treats all basic operations as equally costly, which hides significant differences in time, energy consumption, and cost between different types of computations on modern processors. We propose a weighted-operation complexity model that assigns realistic cost values to different instruction types across multiple dimensions: computational effort, energy usage, carbon footprint, and monetary cost. The model computes overall efficiency scores based on user-defined priorities and can be applied through automated code analysis or integrated with performance measurement tools. This approach complements existing theoretical models by enabling practical, architecture-aware algorithm comparisons that account for performance, sustainability, and economic factors. We demonstrate an open-source implementation that analyzes code, estimates multi-dimensional costs, and provides efficiency recommendations across various algorithms. We address two research questions: (RQ1) Can a multi-metric model predict time/energy with high accuracy across architectures? (RQ2) How does it compare to baselines like Big-O, ICE, and EVM gas? Validation shows strong correlations (\r{ho}>0.9) with measured data, outperforming baselines in multi-objective scenarios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13249 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Metric Algorithmic Complexity: Beyond Asymptotic Analysis Kavun, Sergii Performance Hardware Architecture Computational Complexity Data Structures and Algorithms 68Q25, 68M20, 68W40, 91B74 D.4.8; C.4; F.2.2; K.6.2 Traditional algorithm analysis treats all basic operations as equally costly, which hides significant differences in time, energy consumption, and cost between different types of computations on modern processors. We propose a weighted-operation complexity model that assigns realistic cost values to different instruction types across multiple dimensions: computational effort, energy usage, carbon footprint, and monetary cost. The model computes overall efficiency scores based on user-defined priorities and can be applied through automated code analysis or integrated with performance measurement tools. This approach complements existing theoretical models by enabling practical, architecture-aware algorithm comparisons that account for performance, sustainability, and economic factors. We demonstrate an open-source implementation that analyzes code, estimates multi-dimensional costs, and provides efficiency recommendations across various algorithms. We address two research questions: (RQ1) Can a multi-metric model predict time/energy with high accuracy across architectures? (RQ2) How does it compare to baselines like Big-O, ICE, and EVM gas? Validation shows strong correlations (\r{ho}>0.9) with measured data, outperforming baselines in multi-objective scenarios. |
| title | Multi-Metric Algorithmic Complexity: Beyond Asymptotic Analysis |
| topic | Performance Hardware Architecture Computational Complexity Data Structures and Algorithms 68Q25, 68M20, 68W40, 91B74 D.4.8; C.4; F.2.2; K.6.2 |
| url | https://arxiv.org/abs/2508.13249 |