Proving log(n)

I need help mathmatically proving that a function is Olog(n). I know that 0(n) is linear search. But how would i go about proving a function like this.

-Hash Function-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  unsigned int RSHash(const std::string& str)
{
   unsigned int b    = 378551;
   unsigned int a    = 63689;
   unsigned int hash = 0;

   for(std::size_t i = 0; i < str.length(); i++)
   {
      hash = hash * a + str[i];
      a    = a * b;
   }

   return hash;
}
Ask yourself: what is the n here?

How many times lines 9-10 are repeated?
so my input is "abcdefghijklmnopqrstuvwxyz1234567890" length = 36
9-10 happens 36 times
What if the input is 1000 times longer?
Topic archived. No new replies allowed.