What is the time complexity of following nested dependent loops
Khushit Shah
for(int i = 2; i < N; i ++)
for(int j = 1; j < N; j = j * i)
sum += 1
I got
Can we generalize it further?
kaya3
Using an algebraic identity about logarithms, logᵢ(N) = log N/log i, so we can take log N out as a factor and the summation is then of 1/log i. Approximating this summation as the integral of 1/log x, we get that asymptotically it is O(N/log N), per Wikipedia. Since we previously took out a factor of log N, multiplying by this gives a final result of O(N).
Collected from the Internet
Please contact [email protected] to delete if infringement.
edited at
Related
TOP Ranking
- 1
pump.io port in URL
- 2
How to import an asset in swift using Bundle.main.path() in a react-native native module
- 3
Failed to listen on localhost:8000 (reason: Cannot assign requested address)
- 4
Inner Loop design for webscrapping
- 5
Can't pre-populate phone number and message body in SMS link on iPhones when SMS app is not running in the background
- 6
mysql.connector.errors.InterfaceError: 2003: Can't connect to MySQL server on '127.0.0.1:3306' (111 Connection refused)
- 7
Removed zsh, but forgot to change shell back to bash, and now Ubuntu crashes (wsl)
- 8
ggplotly no applicable method for 'plotly_build' applied to an object of class "NULL" if statements
- 9
How to run blender on webserver?
- 10
Resetting Value of <input type="time"> in Firefox
- 11
Converting a class method to a property with a backing field
- 12
Ambiguous use of 'init' with CFStringTransform and Swift 3
- 13
Execute ./script.sh with a crontab
- 14
How to set tab order for array of cluster,where cluster elements have different data types in LabVIEW?
- 15
How to pass data to the ng2-bs3-modal?
- 16
Retrieve Element Tag Value XML Using Bash
- 17
Spring Boot JPA PostgreSQL Web App - Internal Authentication Error
- 18
SQL Server : need add a dot before two last character
- 19
Making Array From Page Elements in jQuery
- 20
Laravel's ORM sync with timestamps doesn't update timestamps
- 21
Do animations stop css changes after animation completion?
Comments