I am learning Data Structures and Algorithm, I saw a problem in one of the DS book which says to prove
(n + a)^b = O(n^b)
It means that the L.H.S should be equal to Big O of n^b.
I found a solution which says that:
(n+a)^b ≤ cn^b (1)
(n+a)^b ≤ (n+n)^b for n>a and a>0 (2)
(n+n)^b ≤ 2n^b for c=2 and n0 >a
My question is that at line number 2, how did the value became (n+n)^b from (cn^b). It might be a very lame doubt but I am having a hard time in getting it absorbed. I already know anbout Big Theta, Big O and Big Omega notations. I will really appreciate help on this.
this is a very simple thing if you notice, (n+a)^b ≤ cn^b and vice versa. Here, n>a and a>0 so the inequality is if (n+a)^b ≤ cn^b then cn^b will become (n+a)^b or (n+n)^b when the condition applies.
I proved it using the binomial expansion. You can look it and if you carefully notice you will find why cn^b becomes (n+n)^b
you can find binomial solution here