Lemmy: Bestiverse
  • Communities
  • Create Post
  • Create Community
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
RSS BotBM to Hacker NewsEnglish · 9 months ago

What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics

jamesoswald.dev

external-link
message-square
0
link
fedilink
1
external-link

What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics

jamesoswald.dev

RSS BotBM to Hacker NewsEnglish · 9 months ago
message-square
0
link
fedilink
Recently I came across asympotic inequalities of the form $f(x) \le g(x) + O(1)$ in Li and Vitanyi’s An Introduction to Kolmogorov Complexity and Its Applications, where this notion is used to discuss bounds on the complexity of strings. In this post I give a brief definition of what this notation means and how it relates to standard asymptotic notation. Particulary, I’m only going to talk about the case of $O(1)$, but the same ideas can be extended to $O(h(x))$ for any function $h(x)$.

Comments

alert-triangle
You must log in or register to comment.

Hacker News

hackernews

Subscribe from Remote Instance

You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !hackernews@lemmy.bestiver.se
lock
Community locked: only moderators can create posts. You can still comment on posts.

NOTICE: The bot occasionally has downtime, sorry about that. I’m working on adding better monitoring and error recovery so I can get notified faster.

Posts from the RSS Feed of HackerNews.

The feed sometimes contains ads and posts that have been removed by the mod team at HN.

Source of the RSS Bot.

Visibility: Public
globe

This community can be federated to other instances and be posted/commented in by their users.

  • 587 users / day
  • 2.1K users / week
  • 4.14K users / month
  • 8.83K users / 6 months
  • 2 local subscribers
  • 5.8K subscribers
  • 65.5K Posts
  • 36.1K Comments
  • Modlog
  • mods:
  • patrick
  • RSS BotB
  • BE: 0.19.21
  • Modlog
  • Instances
  • Docs
  • Code
  • join-lemmy.org