CODEWITHSUNDEEP
c++big-o
evlvai
evlvai

Reputation: 7

What is the correct Big O of this code

I'm trying to learn Big O notation and I'm a little confused with this C++ code:

void enterElements(int *s1, int s1Size)
{
    for(int x = 0;x < s1Size;++x)
    {
    retry:
        cout<<"Element "<<x + 1<<": ";
        cin>>s1[x];
        int valid = validation();
        if(valid == 1)
        {
            cout<<"The input must be numbers."<<endl;
            goto retry;
        }
    }
}

Because I don't know how to do it well I got 3 results:

  1. 9n + 1 -> O(n)
  2. 7nm + 2m + 2n + 1 -> O(nm)
  3. 7n^2 + 4n + 1 -> O(n^2)

Is any of those correct? If not, can you help me find the correct answer?

int validation()
{
int validation = 0;
if(cin.fail())
{
    validation = 1;
    cin.clear();
    cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n');
}
else
    validation = 0;
return validation;
}

Upvotes: 0

Views: 147

Answers (3)

huseyin tugrul buyukisik
huseyin tugrul buyukisik

Reputation: 11920

Worst condition: never ends (no one told you how to validate a thing)

Best condition: O(n) (if you know how to validate)

Upvotes: 0

lollercoaster
lollercoaster

Reputation: 16503

Big-Oh notation really isn't very applicable here. All you have is a lower bound, there are absolutely no gurantees on validation(), thus the only Big-Oh designation would be O(inf), but that's quite unhelpful.

Your code (should all validations go properly), would be:

Ω(s1Size)

because it WILL be executed s1Size times, not less. Big-Oh notation is not for lower bounds. since we have no guarantee on how many times the goto statement will be used, and therefore no upper bound, so no applicable Big-Oh derivation.

Your runtime, in simple terms: greater than or equal to s1Size iterations (barring an error that causes your loop to exit).

Thus the best case is the above, and the worst case, is well, forever!

EDIT: Ω is correct here, not ω, as Ω implies the runtime is greater than or equal to s1Size

Upvotes: 4

Keith Nicholas
Keith Nicholas

Reputation: 44298

given that it can take user input it can be anything from O(n) to infinity (and beyond :-) )

Upvotes: 0

Related Questions