Question

This has to be written in C language.

What is the execution time growth using Big O notation for a function whose number of primitive operations executed is the following function of the input size: f(N) = 2n^3 + 2^(n+1)

Answer 1

Ignoring constants, the two sub-functions are $n^3$ and $2^n$ . Let us check the values of $n^3$ and $2^n$ at different values of n.

	$n^3$	$2^n$
1	1	2
2	8	4
3	27	8
4	64	16
5	125	32
6	216	64
7	343	128
8	512	256
9	729	512
10	1000	1024
11	1331	2048

For values of n more than or equal to 10,  $2^n$ is more than  $n^3$. So,  $2^n$ has a greater growth rate and hence the time complexity of f(n) is O($2^n$).