Solve the following recurrence by successive substitution method: f(1) — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2022 paper

Module 1: Introduction

20227m

Solve the following recurrence by successive substitution method:
$f(1) = 1 \quad \text{if } n=1$
$f(n) = 3f(n/2) + 6 \quad \text{if } n > 1$

Search Google Ask AI

Similar questions

Design and Analysis of Algorithms Consider the following recurrence relation: T(n) = 2T(n/2) + n Use the substitution method to find an asymptotic upper bound for the function T(n).20237m Design and Analysis of Algorithms Suppose the number of basic operations in an algorithm is defined as: T(n) = T(n-1) + n, with T(1) = 1. Solve this recurrence using the substitution method and determine the time complexity.20247m Design & Analysis of AlgorithmsWrite time function and calculate the time complexity, space complexity and number of function calls of the following pseudocode using substitution method: ``c rec(n) { if (n <= 1) return(1); else { rec(n / 2); for (i = 1; i <= n; i++) printf("algorithm"); } } ``20227m Web TechnologyWrite a program in Java to do the following: (a) To swap the two numbers without using the third variable (b) Factorial of a number using recursion202014m

PreviousKruskal algorithm is a (i) Divide & conquer algorithm (ii) Branch and bound algorithm (iii) Greedy algorithm (iv) Dynamic programming NextWrite the Knuth-Morris-Pratt algorithm for pattern matching. Apply the KMP algorithm for the pattern p = "ababaca" and string s = "bacbabababacaab". Show every step.