Warm tip: This article is reproduced from serverfault.com, please click
algorithm c complexity-theory

What is the time complexity of this little code?

发布于 2020-12-06 17:59:57

What is the time complexity of this little code?

int count = 0;
for (int i = n; i > 0; i = i/2) {
    for (int j = 0; j < i; j++) {
        count++;
    }
}

I want to know the time complexity of this code. To me I calculated as O(n log n) because outer loop runs logn times and inner loop runs O(n) times. But i am confused because the inner loop j depends on i. So what will be the actual time complexity and why?

Questioner
Sazzad Hissain Khan
Viewed
0
分享
chepner 2020-12-07 02:12:15

The exact sum is

n + n/2 + n/4 + ... + 1

which is

n * (1 + 1/2 + 1/4 + ... + 1/n)

The sum of the non-negative powers of 1/2 is well known to approach 2 in the limit, so the total sum approaches 2*n. As a result, the complexity is O(n); i decreases quickly enough to avoid the linarithmic growth.

热门帖子

1
今天碰到的一个看似简单的算法问题卡的我头疼：余额和构成余额的交易的问题，问 GPT 也没结果
2
为什么 Apple TV 平台下为什么免费好用的视频播放器都没有？
3
你们是否意识到人生没有什么保障？
4
中国的男女关系会朝向哪个方向发展呢？日韩法？
5
同学要注册公司，问我借房产证照片？
6
OPNSense clash 透明代理导致部分国内软件无法使用
7
程序员兼职引起的纠纷？
8
IPV6 太香了
9
最近同事的一句话让我一直耿耿于怀，大伙帮忙分析下
10
最便宜 2.5G 的 Wi-Fi6 光猫， F7615TV3 很不错

热门github

1
Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information
2
A Windows and Office activator using HWID / Ohook / KMS38 / Online KMS activation methods, with a focus on open-source code and fewer antivirus detections.
3
Get up and running with Llama 2, Mistral, Gemma, and other large language models.
4
该项目可以让你通过订阅的方式使用Cloudflare WARP+，自动获取流量。This project enables you to use Cloudflare WARP+ through subscription, automatically acquiring traffic.
5
Multi functional app to find duplicates, empty folders, similar images etc.
6
Xray panel supporting multi-protocol multi-user expire day & traffic & ip limit (Vmess & Vless & Trojan & ShadowSocks & Wireguard)
7
The Free Software Media System
8
lightweight, standalone C++ inference engine for Google's Gemma models.
9
📚 Freely available programming books
10
A collective list of free APIs
11
1️⃣🐝🏎️ The One Billion Row Challenge -- A fun exploration of how quickly 1B rows from a text file can be aggregated with Java
12
🎓 Path to a free self-taught education in Computer Science!
13
Curso para aprender el lenguaje de programación Python desde cero y para principiantes. 75 clases, 37 horas en vídeo, código, proyectos y grupo de chat. Fundamentos, frontend, backend, testing, IA...
14
This repository contains System Design resources which are useful while preparing for interviews and learning Distributed Systems
15
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention.