#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2017
    Posts
    22
    Rep Power
    0

    What is the best case (omega) of O(1) expression?


    Let's say that I want to know the best case of some code.
    That segment of code contains:

    Code:
    for(...)
    {
      int x=10;
      int y=20;
      ...
    }
    In this segment, expressions
    Code:
     int x=10;
      int y=20;
    are O(1). What are their omega equivalent?
    Do I need to use O(1) instead in evaluating the best case of a complete code, or do I need to find
    omega equivalents of
    Code:
    int x=10;
      int y=20;
    ?
  2. #2
  3. Lazy Moderator
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    16,260
    Rep Power
    9645
    Big O is not more than, Big Omega is not less than. They're opposites.

    Given that those two statements are pretty much definitely constant time, you can't go much lower than Omega(1). I suppose Omega(0) is possible too if you think that the variables and values are initialized before the code even runs.

    Omega isn't very helpful for a best case analysis. It says "at least as complex as", and for a best case scenario you probably want to know that it's no more complex than. Omega for a worst case would be more appropriate.
    But nobody really uses Omega. It's basically just "best case is O(...)" or "worst case is O(...)". It's not as technically accurate but for that matter Theta is often more correct for a given complexity than O.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2017
    Posts
    22
    Rep Power
    0
    So, you mean, in best case analysis, instead of omega, O notation is used for O(1) expression? Do you mean that there is no omega equivalent of a O(1) expression?

IMN logo majestic logo threadwatch logo seochat tools logo