Question: What is the big-O time complexity of func(p)?
 C++ code follows.

```
int get_power(int a, int b)
{
   if(!b) return 1;
   if(b%2) return a * get_power(a, b/2);
   return get_power(a, b/2);
}
int func(int p)
{
   int sum = 0;
   for(int i = 1; i <= p; ++i) 
   {
      sum += get_power(i, 5);
   }
 return sum;
}

int main()
{
   int c;
   scanf("%d",&c); 
   func(c);
}

```

As per my understanding , the complexity would be O(p) !!
is it correct??? 
by any chance would it be O(p\*log5)

Answer: 
*Sorry for my poor English; I've never written any post including math in English before..*

You seems to misunderstand what `O()` means.

"f(x) is O(g(x))" means there exists `X` which makes it true that `f(x) <= N * g(x)` for each `x > X`, where `N` is constant.

For example, suppose `f(x) = log2 * x`. It's definite that `f(x) <= log2 * g(x)` where `g(x) = x`. so we can say "f(x) is O(x)". *(I said `N` is constant; as you know, `log2` is constant.)*

However, when it comes to `f(x) = x^2`, f(x) is *not* O(x), because `f(x) > N * x` where `x > N`. There *cannot* exist `X` which makes it true that `f(x) <= N * x` where `X > x`.

---

You asked whether the complexity of `func` is `O(p)` or `O(p * log5)`. Answer: **both are true**.

> 
> ...which makes it true that `f(x) <= N * g(x)` where `N` is constant...
> 
> 
> 

As you can know from this sentence, `O(g(x) * log5)` is equal to `O(g(x))`. Constant-multiple doesn't make any effect on `O()`.
The big O notation just defines the limiting behaviour of a function. Therefore the log constant is not required as this does not define its behaviour