algorithm - Solving the recurrence T(n) = T(n / 2) + O(1) using the Master Theorem? -


i'm trying solve recurrence relation find out complexity of algorithm using master theorem , recurrences concepts, how can prove that:

t(n) = t(n/2)+o(1)

is

t(n) = o(log(n)) ?

any explanation apprecciated!!

your recurrence is

t(n) = t(n / 2) + o(1)

since master theorem works recurrences of form

t(n) = at(n / b) + nc

in case have

  • a = 1
  • b = 2
  • c = 0

since c = logba (since 0 = log2 1), in case two of master theorem, solves θ(nc log n) = θ(n0 log n) = θ(log n).

hope helps!


Comments

Post a Comment

Popular posts from this blog

python - How to create a legend for 3D bar in matplotlib? -

Image
given ax = plt.subplot() : ax.bar()[0] can passed plt.legend() . however, ax.bar3d() returns none . how create legend displayed bars? update: passing legend="stuff" ax.bar3d() , calling ax.legend() raises /usr/lib/python2.6/site-packages/matplotlib/axes.py:4368: userwarning: no labeled objects found. use label='...' kwarg on individual plots. warnings.warn("no labeled objects found. " you need use proxy artist legends not supported. this code: from mpl_toolkits.mplot3d import axes3d import matplotlib.pyplot plt import numpy np fig = plt.figure() ax = fig.add_subplot(111, projection='3d') x, y = np.random.rand(2, 100) * 4 hist, xedges, yedges = np.histogram2d(x, y, bins=4) elements = (len(xedges) - 1) * (len(yedges) - 1) xpos, ypos = np.meshgrid(xedges[:-1]+0.25, yedges[:-1]+0.25) xpos = xpos.flatten() ypos = ypos.flatten() zpos = np.zeros(elements) dx = 0.5 * np.ones_like(zpos) dy = dx.copy() dz = hist.flatten() ax...
Read more

java - Multi-Label Document Classification -

i have database in store data based upon following 3 fields: id, text, {labels}. note each text has been assigned more 1 label \ tag \ class. want build model (weka \ rapidminer \ mahout) able recommend \ classify bunch of labels \ tags \ classes given text. i have heard svm , naive bayes classifier, not sure whether support multi-label classification or not. guides me right direction more welcome! the basic multilabel classification method one-vs.-the-rest (ovr), called binary relevance (br). basic idea take off-the-shelf binary classifier, such naive bayes or svm, create k instances of solve k independent classification problems. in python-like pseudocode: for each class k: learner = svm(settings) # example labels = [class_of(x) == k x in samples] learner.learn(samples, labels) then @ prediction time, run each of binary classifiers on sample , collect labels predict positive. (both training , prediction can done in parallel, since problems assumed ...
Read more

php - Dynamic url re-writing using htaccess -

how can rewrite http://mydomain.com/test/master.php?catid=2&subcatid=8 http://mydomain.com/test/master.php/catname/subcat using .htaccess file. once rewritten, how can access these parameters in master.php? note: untested, let me know if doesn't work. rewriterule ^master.php/([a-za-z0-9_-]+)/([a-za-z0-9_-]+)$ /master.php?catid$1&subcatid=$2 [l]
Read more