Nobel Prize in Economics
     
  Algorithms Textbook 

Categories




Most popular tags

asymptotic-analysis recurrence-relations time-complexity loops asymptotic-notation graph dynamic-programming greedy substitution-method analysis a-star np-completeness nested-loops vertex-coloring mdp log probability stochastic heuristic master-theorem markov-model n-puzzle csp graph-coloring exam mvcs small-oh exponent proof viterbi bayes-rule hmm tree-search grid-world admissible n-queens conflict ai clique coins reduction dfs prime-numbers sqrt count easy sorted-lists logn example recursive gcd independent-set unsolvable pcp counter-example not-master-theorem modulus algebra most-likely-estimate reinforcement-learning direct-evaluation meu articulation-point hotel-room small-omega limit-method mle graph-search while-loop greedy-suboptimal job-assignment maximize-value gold constraint-satisfaction-problem 8-puzzle task-environments min-max peak randomized satisfiability random-graph-generation proxy network sudoku branchandbound d&c degree-constrained spanning-tree vertex-cover branch subtree series pmi bound contradiction math backtracking tree minimize floors

Solve the recurrence relation: T(n)=T(n/2)+T(n^0.5)+n

+3 votes
in Asymptotic Analysis by Active (276 points)

1 Answer

+1 vote
 
Best answer
Simple guess that anyone can make is that T(n) = O(n). This can be proved using PMI.

Further, since T(n) includes n, we know that T(n) = Big Omega(n).  Therefore, we can reach the conclusion that T(n) = Theta(n).
by AlgoMeister (1.6k points)
selected by

Related questions

 | Snow Theme by Q2A Market
Powered by Question2Answer
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...