Let n denote a positive integer. A function f is defined as
f(n) = 0, if n = 1
f(n) = f(⌊n/2⌋) + 1, if n > 1
What is f(25), and what does this function find?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. 4, ⌊log2 n⌋
Explanation
f(25) = f(12)+1 = f(6)+2 = f(3)+3 = f(1)+4 = 4. Halving until 1 counts ⌊log2 n⌋ steps (⌊log2 25⌋ = 4).More Data Structures and Algorithms questions
- Given the FFT, we can have a ______ time procedure for multiplying two polynomials A(x) and B(x) of degree bound n, where input and output…
- Circuit satisfiability problem: given a Boolean combinational circuit composed of AND, OR and NOT gates, is it satisfiable? A one-output Bo…
- Given the expression (A + B * D) / (E − F) + G: 1. The prefix notation is + / + A * D B − E F G 2. The prefix expression is the reverse of…
- Match List I with List II. Choose the correct answer from the options given below:List I List II a. Dijkstra's algorithm I. Calculates path…
- For the weighted graph below, which of the following orders of adding edges can NOT be produced by a minimum spanning tree algorithm? Edges…
- Statement I: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to f…