Czas wyszukiwania binarnego.

Witam!
Mam za zadanie zbadać złożoność pesymistyczną wyszukiwania liniowego i binarnego w tablicy o rozmiarze ~ 2^28. O ile wyszukiwanie liniowe poszło mi całkiem zgrabnie to z binarnym mam problem. Chcę zmierzyć czas wyszukiwania ostatniego elementu w tablicach o rozmiarze co 9000000. Nie mogę sobie z tym poradzić. Proszę o pomoc.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace binarne
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch stoper = new Stopwatch();

            // n rozmiar tablicy
            int[] tablica = new int[268435456];

            for (int i = 0; i < tablica.Length; i++)
            {
                tablica[i] = i;
            }
            
            int s;

            int n = tablica.Length;
            int p = 0;
            int o = 0;
            s = (p + o) / 2;


            for (o = 0; o < tablica.Length; o += 9000000)
                
            {
                for (int x = 0; x < tablica.Length; x += 9000000)
                {
                    stoper.Start();
                    binarne(tablica, x, n, p, o, s);
                    stoper.Stop();


                    Console.WriteLine("{0}\t{1}", x, stoper.ElapsedTicks * 1.0 / Stopwatch.Frequency);
                    stoper.Reset();


                }
            }
               



        }
        static bool binarne(int[] t, int x, int n, int p, int o, int s)
        {
            while (p <= o)
            {
                s = (p + o) / 2;

                if (t[s] == x)
                {
                    return true;
                }

                if (t[s] < x)
                    p = s + 1;
                else
                    o = s - 1;
            }
            return false;
        }
    }
}