Appropriate complexity notation for representing this algorithm

Question

I was hoping to get some help assessing the best way to notated the complexity of the following algorithm (Written in psuedo-code):

Input N;

bool complete = false;

If(N Satisfies Condition A)
{
    K = N/6;
    For(int i = 1; i <= sqrt(K/6) && complete != true; i++)
    {
        If(K Satisfies Condition B based on i)
                  complete = true;
        Else if(K Satisfies Condition C based on i)
                   complete = true;
        Else if(K satisfies Condition D based on i)
                   complete = true;
        Else if(K satisfies Condition E based on i)
        {
               If(K satisfies Condition D based on (i + 1))
               {
                        Change Output;
                        complete = true;
                }
                Else
                        complete = true;
         }
         Else if(K satisfies Condition F based on i)
         {
                change output;
                continue;
         }
     }
}

I am familiar with big O-Notation, but that (from what I understand) applies most specifically to worst-cases. However, this algorithm rarely meets that worst case scenario (Which would be O(sqrt(N)) if only Condition F is met). I would have to say at least 95% of inputs N however don't meet that worst case scenario.

With that embedding if-statement in meeting Condition E, I have found very interesting results. As soon as Condition E is met, the program is essentially complete. It resembles very closely to a constant O(1), other than the few rare cases of Condition F.

For Example:

N = 11, Time = 0.004 sec, Steps Taken = 0
N = 101, Time = 0.005 sec, Steps Taken = 1
N = 1001, Time = 0.004 sec, Steps Taken = 0
N = 10001, Time = 0.003 sec, Steps Taken = 1
N = 100001, Time = 0.004 sec, Steps Taken = 1

Don't Try to look for a pattern there though, look at the results for some random and much much larger values:

N = 12764787846358441471, Time = 0.007, Steps Taken = 3332
N = 18446744073709551557, Time = 0.005, Steps Taken = 7

So as you can see, almost all times stay close to about 0.006 seconds (on my machine), and even though the steps vary, it isn't consistent in any direction. This algorithm is one I developed for a paper I'm working on, and so I am not only open to Big O-notation to represent this algorithm, I just want some way to factually represent it's average-case results which tend to be very very good. Any insight on at least directions to look into is appreciated. My math knowledge greatly outweighs that of my CS knowledge as of now, so my exposure to this kind of thing is minimal.

Thanks, DevenJ

Answer 1

What is sure about your algorithm is that it is:

• O(1) in the best case,
• O(sqrt(n)) in the worst case.

To find the average running time, you will have to run your algorithm on random inputs and draw a graph representing runtime or number of steps in function of input size. Then you smooth your points to try to fit them to a function. By drawing that graph, you will find that your average time complexity is probably O(1) in the average case too.