This paper presents a refined complexity calculus model: r-Complexity, a new asymptotic notation that offers better complexity feedback for similar programs than the traditional Bachmann-Landau notation, providing subtle insights even for algorithms that are part of the same conventional complexity class. The architecture-dependent metric represents an enhancement that provides better sensitivity with respect to discrete analysis.
This study investigates whether analyzing the code comments available in the source code can effectively reveal functional similarities within software. The authors explore how both machine-readable comments (such as linter instructions) and human-readable comments (in natural language) can contribute towards measuring the code similarity. For the former, the work is relying on computing the cosine similarity over the one-hot encoded representation of the machine-readable comments, while for the latter, the focus is on detecting similarities in English comments, using threshold-based computations against the similarity measurements obtained using models based on Levenshtein distances (for form-based matches), Word2Vec (for contextual word representations), as well as deep learning models, such as Sentence Transformers or Universal Sentence Encoder (for semantic similarity). For evaluation, this research has analyzed the similarities between different source code versions of the open-source code editor, VSCode, based on existing ESlint-specific directives, as well as applying natural language processing techniques on incremental releases of Kubernetes, an open-source system for automating containerized application management. The experiments outlines the potential for detecting code similarities solely based on comments, and observations indicate that models like Universal Sentence Encoder are providing a favorable balance between recall and precision. This research is integrated into Project Martial, an open-source project for automatic assistance in detecting plagiarism in software.
This paper presents a series of general properties of the r-Complexity calculus, a complexity measurement for assessing the performance and asymptotic behaviour of real-world algorithms. This research describes characteristics such as reflexivity, transitivity, or symmetry and discusses several conversion rules between different classes of r-Complexity, as well as establishing fundamental arithmetic principles. The work also examines the behaviour of the addition property within this system and compares its characteristics with those frequently used in the traditional Bachmann-Landau notation. Through utilizing these properties, this research seeks to promote the exploration and development of novel applications for r-Complexity, as well as accelerating the adoption rate of calculus in this refined complexity model.