The Gateway to Computer Science Excellence
0 votes
33 views
Show that for any real constants $a$ and $b$, where $b > 0,$
$(n+a)^b=\Theta(n^b)$
in Algorithms by Boss (41.8k points) | 33 views

1 Answer

0 votes
Best answer
According to binomial theorem,

$\large (n+a)^b = \binom{b}{0}n^b a^0 + \binom{b}{1}n^{b-1} a^1 + \binom{b}{2}n^{b-2} a^2 + ...... + \binom{b}{b}n^{0} a^b$

term with largest power of n after expansion is $\large \binom{b}{0}n^b a^0 = n^b$ and for calculating $\Theta$ we can ignore other terms with less power of n.

Hence,

$(n+a)^b=\Theta(n^b)$
by Boss (35.4k points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,242 answers
194,286 comments
95,934 users