嵌套循环时间复杂度分析：寻求无需工具的简便分析方法

我正在计算一段嵌套while循环的时间复杂度，循环的核心逻辑如下：

• 外层循环：变量i从1开始，每次翻倍（i *= 2），直到i > n时终止
• 内层循环：变量j从n开始，每次减半（j /= 2），直到j < i时终止

我已经通过观察迭代规律完成了初步分析：

• 外层循环的前n/2次迭代中，内层循环仅执行1次（首次外层循环内层无执行，不影响渐近时间复杂度分析）
• 接下来n/4次外层迭代中，内层循环执行2次
• 以此类推，最终推导出求和式：$\sum_{k=1}^{\log_2 n} k \cdot \frac{n}{2^{k+1}}$

当n趋近于无穷大时，该求和式可简化为2n，因此算法的时间复杂度为O(n)。

我的问题是：有没有更简便的分析技巧？这次我借助工具完成了求和式的简化，但考试仅允许使用基础计算器，无法依赖外部工具。

内容的提问来源于stack exchange，提问作者tobias ingold