Design and Analysis of Algorithms

Answer: (ii) Memory required to run an algorithm

Space complexity = total memory (input + auxiliary + program). Time is execution steps.

Answer: (iii) Definiteness

• Finiteness: terminates after finite steps
• Definiteness: each step unambiguous
• Effectiveness: each step basic feasible
• Generality: works for all inputs of type

Answer: (i) O-notation

• O = upper bound (worst-case)
• Ω = lower bound (best-case)
• Θ = tight bound (average-case when upper=lower)
  Worst-case expressed with Big-O.

Answer: (ii) max{ f(n), g(n)} (which equals (iv) f+g asymptotically)

If algorithm has two independent parts sequentially, T = f+g = Θ(max). Sum asymptotically dominated by max. Both (ii) and (iv) are correct; exam expects (ii) max as simplified.

Answer: (ii) O(n²)

5n² dominates 3n+7; tight upper bound is O(n²). O(n³) also upper but not minimal.

Correct option: (ii) The lower bound (as the intended distinction in this question).

Big-Ω (Omega) notation describes an asymptotic lower bound on a function's growth. Formally, (f(n) \in \Omega(g(n))) if there are constants (c>0) and (n_0) such that (f(n) \ge c,g(n)) for every (n \ge n_0).

Important clarification: Big-Ω does not inherently mean best-case complexity. Upper bound, lower bound and tight bound are properties of asymptotic notation; best-case, worst-case and average-case describe which case of an algorithm's input behaviour is being analysed. A lower bound can be applied to any of those functions.

• Big-O: asymptotic upper bound.
• Big-Ω: asymptotic lower bound.
• Big-Θ: asymptotically tight bound.

Therefore, choose option (ii) for the lower-bound part, but do not memorize “Ω = best case” as a general rule.

Answer: (ii) O(log n)

Master theorem: a=1,b=2,f=1,n^{log_b a}=1 → case 2 with f=Θ(n^{0}) → Θ(log n).

Answer: (iii) Insertion sort

Insertion sort stable O(n²) worst, adaptive O(n) nearly sorted. Merge stable O(n log n), Quick unstable, Selection unstable. Question expects insertion.

Answer: (iii) Θ(n² log n)

Master: a=2,b=4, n^{log_b a}=n^{0.5}. f=n² log n dominates → case 3 → Θ(f)=Θ(n² log n). Regularity holds.

Answer: (iv) $(100)^{(\log n)^{1/3}} + (\log \log n)^{2/3}$ is asymptotically smallest

Explanation:

Take logs or compare growth orders:

• (i) $2^n = e^{n \ln 2} = e^{\Theta(n)}$ → exponential
• (ii) $n^{\log n}= e^{(\log n)(\ln n)} = e^{\Theta((\log n)^2)}$
• (iii) $n^{\sqrt n}= e^{\sqrt n \cdot \ln n}= e^{\Theta(\sqrt n \log n)}$
• (iv) $(100)^{(\log n)^{1/3}} = e^{(\ln 100)(\log n)^{1/3}} = e^{\Theta((\log n)^{1/3})}$ plus $(\log\log n)^{2/3}= e^{\Theta(\log\log\log n)}$ which is doubly logarithmic.

For large $n$: $(\log n)^{1/3} \ll (\log n)^2 \ll \sqrt n\log n \ll n$.

Hence ordering from smallest to largest: (iv) $\ll$ (ii) $\ll$ (iii) $\ll$ (i).

Formally $f_4 = n^{o(1)}$ (sub-polynomial, quasi-polylog), $f_2 = n^{\Theta(\log n)}$ (super-polynomial but sub-exponential), $f_3 = 2^{\Theta(\sqrt n \log n)}$, $f_1=2^{\Theta(n)}$.

Correct choice: (iv)

Note: Options (ii) and (iii) are often swapped in ranking; but both dominate (iv) asymptotically.

Answer: (ii) The amount of physical memory used

Explanation:

• Space complexity is the total amount of memory (in terms of asymptotic function of input size $n$) required by an algorithm to run to completion, including:

  • Input space / auxiliary space for variables, data structures, recursion stack, dynamically allocated memory.
  • Often reported as auxiliary space (extra space excluding input itself).

• (i) number of input elements is $n$ itself, not space complexity.

• (iii) number of recursive calls contributes to stack space but is only one component.

• (iv) lines of code is program size / software metric, unrelated to asymptotic memory usage.

Hence space complexity = memory consumed as function of $n$, e.g., iterative linear search $O(1)$, merge sort $O(n)$, recursive DFS $O(h)$ stack.

Correct choice: (ii)

Answer: (iv) $8/3 \approx 2.67$

Explanation:

Merge of two sorted lists $A=[a_1<a_2]$, $B=[b_1<b_2]$ with all 4! / (2!2!) = 6 interleavings equally likely (distinct elements, random order). Standard merge:

 i=j=0, comps=0
 while i<2 and j<2: comps++; if A[i]<B[j] i++ else j++

Best case = 2 comps (one list entirely smaller: $a_1<a_2<b_1<b_2$ or $b_1<b_2<a_1<a_2$)
Worst case = 3 comps (interleaved).

Enumerate:

1. $a_1<a_2<b_1<b_2$: $a_1\!<\!b_1$, $a_2\!<\!b_1$ → 2
2. $a_1<b_1<a_2<b_2$: $a_1\!<\!b_1$, $b_1\!<\!a_2$, $a_2\!<\!b_2$ → 3
3. $a_1<b_1<b_2<a_2$: $a_1\!<\!b_1$, $b_1\!<\!a_2$, $b_2\!<\!a_2$ → 3
4. $b_1<b_2<a_1<a_2$: 2 (symmetric to 1)
5. $b_1<a_1<b_2<a_2$: 3
6. $b_1<a_1<a_2<b_2$: 3

Average = $(2+3+3+2+3+3)/6 = 16/6 = 8/3$.

Worst-case merging $m+n-1 =3$, best $\min(m,n)=2$, average $8/3$.

Correct choice: (iv) $8/3$

Asymptotic Notations — $O$, $\Omega$, $\Theta$

Asymptotic notation describes growth of $T(n)$ for large $n$, ignoring constants and lower-order terms.

1. Big O — Upper bound ($\le$)

$$O(g(n)) = \{ f(n): \exists c>0, n_0>0, 0 \le f(n) \le c\,g(n) \;\forall n \ge n_0 \}$$
Example: $3n^2+5n+2 = O(n^2)$ (choose $c=4$, $n_0=10$). Means algorithm at most that fast-growing.

2. Big Omega — Lower bound ($\ge$)

$$\Omega(g(n)) = \{ f(n): \exists c>0, n_0>0, 0 \le c\,g(n) \le f(n) \;\forall n \ge n_0 \}$$
Example: $n^2/2 - n = \Omega(n^2)$. Means algorithm at least that slow.

3. Big Theta — Tight bound ($=$)

$$\Theta(g(n)) = \{ f(n): \exists c_1,c_2>0, n_0>0, c_1 g(n) \le f(n) \le c_2 g(n) \;\forall n \ge n_0 \}$$
Equivalently $f(n)=\Theta(g(n)) \iff f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$.
Example: $3n^2+5n = \Theta(n^2)$.

Small o / small omega (strict)

• $o(g)$: $\forall c>0$ eventually $f(n) < c g(n)$ (non-tight upper).
• $\omega(g)$: strict lower.

Properties & Use

• Transitivity, reflexivity, symmetry ($\Theta$ symmetric).
• Transpose: $f=O(g) \iff g=\Omega(f)$.
• Used to classify algorithms: Linear search $O(n)$ worst, $\Omega(1)$ best, $\Theta(n)$ average; Merge sort $\Theta(n\log n)$; Binary search $\Theta(\log n)$.
• Hierarchy: $O(1) \subset O(\log n) \subset O(n) \subset O(n\log n) \subset O(n^2) \subset O(2^n)$.

Graphical intuition

Plot $c\cdot g(n)$ bounding $f(n)$ above ($O$), below ($\Omega$), or sandwiching ($\Theta$) beyond $n_0$.

Solution – Recurrence $f(n)=3f(n/2)+6$, $f(1)=1$ by Successive Substitution

Assume $n=2^k$ ($k=\log_2 n$).

Unfold:
$$\begin{aligned} f(n) &= 3f(n/2)+6 \\ &= 3[3f(n/4)+6]+6 = 3^2 f(n/2^2)+6\cdot3+6 \\ &= 3^2[3f(n/2^3)+6]+6\cdot3+6 = 3^3 f(n/2^3)+6\cdot3^2+6\cdot3+6\\ &\;\vdots \\ f(n) &= 3^k f(n/2^k)+6\sum_{i=0}^{k-1}3^i \end{aligned}$$

Since $n/2^k=1$, $f(n/2^k)=f(1)=1$ and $\sum_{i=0}^{k-1}3^i = (3^k-1)/(3-1)=(3^k-1)/2$.

$$f(n)=3^k \cdot 1 +6\cdot\frac{3^k-1}{2}=3^k+3(3^k-1)=4\cdot3^k-3$$

With $k=\log_2 n$:
$$\boxed{f(n)=4\cdot 3^{\log_2 n}-3 = 4\cdot n^{\log_2 3}-3}$$ for $n$ power of 2.

Asymptotics:
$$f(n)=\Theta(n^{\log_2 3}) = \Theta(n^{1.58496\dots})$$

Check by Master Theorem: $a=3$, $b=2$, $n^{\log_b a}=n^{\log_2 3}$ dominates $f(n)=\Theta(1)$ case 1 → $\Theta(n^{\log_2 3})$ consistent.

For general $n$ (not power of 2), embed between powers of 2 → same $\Theta$.

(i) Best / Worst / Average Case Complexity

• Best case $T_{best}(n)$: minimum time over all inputs of size $n$. Often overly optimistic.
• Worst case $T_{worst}(n)$: maximum time — guarantee that algorithm never exceeds this.
• Average case $T_{avg}(n)$: expected time over distribution (usually uniform) of inputs — needs probabilistic analysis.

(ii) Example: Linear Search for key $x$ in array $A[1..n]$

for i=1..n: if A[i]==x return i
return -1

• Best: $x=A[1]$ → 1 comparison → $\Theta(1)$ → $O(1)$ / $\Omega(1)$.
• Worst: $x
  otin A$or$x=A[n]$→$n$comparisons →$\Theta(n)$.
• Average (uniform, $x$ always present): expected position $(n+1)/2$ → $\Theta(n)$ comparisons; if $x$ absent with probability $p$, average = $p\cdot n + (1-p)(n+1)/2 =\Theta(n)$.

Similarly Binary Search: best $O(1)$, worst/avg $\Theta(\log n)$; Bubble Sort: best $O(n)$ (with early exit), worst/avg $\Theta(n^2)$.

(iii) Why Worst-Case Preferred

1. Guarantee: bounds response time for real-time / safety-critical systems.
2. Simplicity: does not require input distribution knowledge (average case needs distribution).
3. Dominant for many algorithms: average = worst order-wise (e.g., linear search, quicksort worst $O(n^2)$ but average $O(n\log n)$ — here worst still informs; randomized analysis gives expected worst over random choices).
4. Adversarial inputs: worst-case protects against malicious data.
5. Standard in complexity theory: $P$, $NP$ defined via worst-case polytime.

Note: Average-case is important when worst-case is rare (e.g., QuickSort, Hashing expected $O(1)$), but worst-case remains the default metric published.

Time and Space Complexity + Algorithm to Add $n$ Naturals

Definitions

• Time Complexity: asymptotic number of basic operations (steps) as function of input size $n$, $T(n)$.
• Space Complexity: asymptotic total memory (input + auxiliary + recursion stack) $S(n)$; often reported as auxiliary space (extra beyond input).

Algorithm — Sum of First $n$ Natural Numbers

Iterative $O(n)$ time, $O(1)$ aux space:

Algorithm SumNatural(n):
  sum ← 0
  for i ← 1 to n:
    sum ← sum + i
  return sum

Time: $n$ iterations × $O(1)$ → $T(n)=\Theta(n)$ ($n$ additions). Space: variables $sum$, $i$, $n$ → 3 words → $S(n)=\Theta(1)$ auxiliary ($\Theta(n)$ if counting input array? Here input is just $n$ → $O(1)$).

Formula $O(1)$ time (mathematical):

Algorithm SumFormula(n):
  return n*(n+1)//2

Time $\Theta(1)$ arithmetic operations, space $\Theta(1)$. Uses closed form $\sum_{i=1}^n i = n(n+1)/2$.

Recursive (for illustration):

RecSum(n): if n==1 return 1 else return n + RecSum(n-1)

Time $\Theta(n)$, stack space $\Theta(n)$ due to $n$ frames — worse.

Analysis Summary

Variant	Time	Auxiliary Space	Total Space
Iterative loop	$\Theta(n)$	$O(1)$	$O(1)$
Formula	$\Theta(1)$	$O(1)$	$O(1)$
Recursive	$\Theta(n)$	$\Theta(n)$ stack	$\Theta(n)$

Best practical: formula $O(1)$. If required to demonstrate space complexity concept, loop shows $O(1)$ auxiliary despite $O(n)$ time.

$T(n)=2T(n/2)+n$ — Substitution Method, Upper Bound $O(n \log n)$

Guess: $T(n) \le c\, n \log n$ for some $c>0$, $n\ge n_0$ (with $T(1)=\Theta(1)$).

Inductive Hypothesis: Assume for $n/2$: $T(n/2) \le c (n/2) \log(n/2)$.

Inductive Step:
$$\begin{aligned} T(n) &= 2T(n/2)+n \\ &\le 2\left[ c\frac{n}{2}\log\frac{n}{2}\right]+n \\ &= c n (\log n - \log 2)+n \\ &= c n \log n - c n \log 2 + n \end{aligned}$$
With $\log$ base 2, $\log 2=1$:
$$T(n) \le c n \log n -c n + n = c n \log n -(c-1)n$$
Choose $c \ge 1$ → $-(c-1)n \le 0$ → $T(n) \le c n \log n$.

Base case: Need $T(1) \le c\cdot1\cdot\log1 =0$ fails for log base2. Use $T(2)$ or define $T(1)=1$, choose $n_0=2$, pick $c$ large enough: $c\cdot2\log2 \ge T(2)=2T(1)+2=4$ → $c\ge2$ works. More formally prove for $n\ge2$, or use $n\log n$ with $T(1)=\Theta(1)$ and show $T(n)\le c n\log n +b$ variant.

Hence $T(n)=O(n\log n)$.

Tight bound: Similarly show $T(n) \ge c' n\log n$ → $\Omega(n\log n)$ → $\Theta(n\log n)$.
By Master Theorem case 2 ($a=2$, $b=2$, $n^{\log_b a}=n^1$, $f(n)=n=\Theta(n^{\log_b a})$) → $T(n)=\Theta(n\log n)$.

Application: This is the Merge Sort recurrence.

$T(n)=T(n-1)+n$, $T(1)=1$ — Solve by Iteration / Substitution

Iterative Unfolding:
$$\begin{aligned} T(n) &= T(n-1)+n \\ &= [T(n-2)+(n-1)]+n = T(n-2)+(n-1)+n \\ &= [T(n-3)+(n-2)]+(n-1)+n \\ &\;\vdots \\ &= T(1) + 2+3+\dots+n \\ &= 1 + \sum_{k=2}^{n} k = \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \end{aligned}$$

Substitution Proof: Guess $T(n)=n(n+1)/2$.

• Base $n=1$: $1\cdot2/2=1$ ✓
• Step: assume $T(n-1)=(n-1)n/2$ → $T(n)=(n-1)n/2 + n = n(n+1)/2$ ✓

Asymptotics:
$$T(n)=\frac{n^2}{2}+\frac{n}{2}=\Theta(n^2) = O(n^2), \Omega(n^2)$$

Application: Sum of first $n$ naturals; time of naive incremental algorithms (e.g., insertion sort worst-case without divide).

Asymptotic Notations & Properties

Definitions (as in Q36)

• $O(g)$ upper: $\exists c,n_0: 0\le f(n)\le c g(n)$ $\forall n\ge n_0$.
• $\Omega(g)$ lower: $\exists c,n_0: 0\le c g(n)\le f(n)$.
• $\Theta(g)$ tight: $c_1 g(n)\le f(n)\le c_2 g(n)$ → $O \cap \Omega$.
• $o(g)$ strict upper: $\forall c>0$ $f(n)<c g(n)$ eventually ($f/g\to0$).
• $\omega(g)$ strict lower ($f/g\to\infty$).

Properties

1. Transitivity: $f=O(g), g=O(h)\Rightarrow f=O(h)$ (similar for $\Omega,\Theta$).
2. Reflexivity: $f=\Theta(f)$.
3. Symmetry: $f=\Theta(g)\iff g=\Theta(f)$; transpose symmetry $f=O(g)\iff g=\Omega(f)$.
4. Additivity/Max rule: If $f_1=O(g_1), f_2=O(g_2)$ then $f_1+f_2=O(\max(g_1,g_2))$. Hence polynomial $a_k n^k+\dots=O(n^k)$.
5. Scaling: $c f(n)=\Theta(f(n))$ for constant $c>0$; lower-order terms absorbed.
6. Ordering: $O(1)\subset O(\log n)\subset O(n)\subset O(n\log n)\subset O(n^2)\subset O(n^3)\subset O(2^n)\subset O(n!)$.
7. Polynomial gap: $n^{a}=o(n^{b})$ if $a<b$; any poly is $o(2^n)$.
8. Master/recurrence use: notations hide constants allowing comparison Unabhängig von Hardware.

Example Hierarchy

• Linear search worst $\Theta(n)$, binary $\Theta(\log n)$, merge $\Theta(n\log n)$, matrix mult naive $\Theta(n^3)$, Strassen $\Theta(n^{2.81})$, TSP brute $\Theta(n!)$.

Pitfalls

• $O$ is not tight — use $\Theta$ when both upper and lower known.
• Not all functions comparable ($n^{\sin n}$ incomparable).
• Amortized vs worst-case: $O$ still worst over sequence.

Master's Theorem — Statement & Applications

Theorem

For $T(n)=aT(n/b)+f(n)$, $a\ge1$, $b>1$:
Let $c=\log_b a$.

• Case 1: $f(n)=O(n^{c-\epsilon})$ → $T(n)=\Theta(n^{c})$ (leaf heavy).
• Case 2: $f(n)=\Theta(n^{c}\log^{k} n)$ → $T(n)=\Theta(n^{c}\log^{k+1} n)$; with $k=0$ → $\Theta(n^{c}\log n)$ (balanced).
• Case 3: $f(n)=\Omega(n^{c+\epsilon})$ + regularity $a f(n/b)\le c' f(n)$ → $T(n)=\Theta(f(n))$ (root heavy).

(i) $T(n)=2T(n/2)+n$

• $c=\log_2 2=1$ → $n^{c}=n$, $f(n)=n=\Theta(n^{c})$ → Case 2 (k=0) → $$T(n)=\Theta(n\log n)$$ (Merge Sort).

(ii) $T(n)=3T(n/2)+n^2$

• $c=\log_2 3 \approx1.585$, $n^{c}=n^{1.585}$, $f(n)=n^2=\Omega(n^{c+\epsilon})$ with $\epsilon\approx0.415$.
• Regularity: $3(n/2)^2=3n^2/4 \le c f(n)$ with $c=3/4<1$ holds → Case 3 → $$T(n)=\Theta(n^2)$$
  Alternatively leaf vs root: root dominates.

(iii) $T(n)=2T(n/2)+n/\log n$

• $c=1$ → $n^{c}=n$, $f(n)=n/\log n = \Theta(n^{c}/\log n)$.
• This is not polynomially smaller ($n^{c-\epsilon}$) nor $\Theta(n^{c})$; it is $n/\text{polylog}$ — gap between cases 1 and 2.
• Master Theorem does NOT apply (fails polynomial gap condition). By recursion tree / Akra-Bazzi:
  $$T(n)=2T(n/2)+n/\log n\;\Rightarrow\; T(n)=\Theta(n\log\log n)$$
  Proof sketch: $T(n)=n\sum_{i=0}^{\log n -1} 1/(\log n -i)=n H_{\log n}=n\cdot\Theta(\log\log n)$.
• If forced into extended Case 2 ($k=-1$), some extensions give $\Theta(n\log\log n)$.

Summary: (i) $\Theta(n\log n)$ Case2, (ii) $\Theta(n^2)$ Case3, (iii) Gap case — $\Theta(n\log\log n)$, master not applicable in strict form.

Master Theorem Applications

General Form: $T(n)=aT(n/b)+f(n)$, $a\ge1$, $b>1$, $f(n)$ asymptotically positive.
Let $n^{\log_b a}$ be the watershed.

• Case 1: $f(n)=O(n^{\log_b a -\epsilon})$ for $\epsilon>0$ → $T(n)=\Theta(n^{\log_b a})$.
• Case 2: $f(n)=\Theta(n^{\log_b a}\log^k n)$ → $T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$; special $k=0$: $\Theta(n^{\log_b a}\log n)$.
• Case 3: $f(n)=\Omega(n^{\log_b a+\epsilon})$ and regularity $a f(n/b)\le c f(n)$ for $c<1$ → $T(n)=\Theta(f(n))$.

(i) $T(n)=4T(n/2)+n^3$

• $a=4$, $b=2$ → $n^{\log_b a}=n^{\log_2 4}=n^2$.
• $f(n)=n^3=\Omega(n^{2+1})$ with $\epsilon=1$.
• Regularity: $4(n/2)^3 =4 n^3/8 = n^3/2 \le c n^3$ with $c=1/2<1$ ✓
• Case 3 → $$T(n)=\Theta(f(n))=\Theta(n^3)$$

(ii) $T(n)=T(n/2)+2^n$

• $a=1$, $b=2$ → $n^{\log_b a}=n^0=1$.
• $f(n)=2^n$ is exponential, not polynomial; $2^n = \Omega(n^{\epsilon})$ for any $\epsilon$, dominated by $f$.
• Although $f(n)=2^n = \Omega(n^{0+\epsilon})$, regularity holds: $1\cdot2^{n/2} \le c 2^n$ for large $n$ ($c=1/2$) as $2^{n/2}/2^n=2^{-n/2}\to0$.
• This fits Case 3 (generalized interpretation) where $f$ dominates polynomially. Hence $$T(n)=\Theta(f(n))=\Theta(2^n)$$

Note: Strict Master theorem in many textbooks requires $f$ polynomial; for exponential $f$, the theorem still yields $T(n)=\Theta(2^n)$ because $n^{\log_b a}=O(f(n))$ and regularity holds; formally the answer is exponential dominated, not $\Theta(1)$. Some state "Master theorem not applicable (f not polynomial)" but via extension the bound is $\Theta(2^n)$; if insisting on polynomial $f$ condition, declare not applicable, recurrence solves to $\Theta(2^n)$ by recursion tree: $T(n)=2^n+2^{n/2}+2^{n/4}+\dots+1 =\Theta(2^n)$.

Linear Search for 7 in $A=[3,5,2,8,7,1,4]$

Algorithm

LinearSearch(A, n, key):
  for i=0 to n-1:
    if A[i]==key: return i  // 0-based index, +1 for 1-based position
  return -1 // not found

Trace for key=7

i (0-based)	A[i]	Compare A[i]==7?	Action
0	3	3==7? No	continue
1	5	5==7? No	continue
2	2	2==7? No	continue
3	8	8==7? No	continue
4	7	7==7? Yes	return 4 (0-based) / 5 (1-based)
Search stops early; elements after index4 not examined.

Result: Found at index 4 (0-based) → position 5 (1-based). Comparisons = 5 best/worst?

Complexity Analysis ($n=7$)

• Time:
  • Best $O(1)$ (key at first position)
  • Worst $O(n)$ (key absent or at last) → here worst would be 7 comparisons
  • Average $O(n)$ → expected $(n+1)/2$ if key present uniformly
  • In this instance 5 comparisons = $\Theta(n)$ worst-like.
• Space: $O(1)$ auxiliary (loop variable + key), $O(n)$ total if counting input array; in-place.
• No sorting needed; works on unsorted arrays; optimal for unsorted (any algorithm must examine $\Omega(n)$ in worst case).

Master's Theorem & $T(n)=2T(n^{1/2})+\log n$

Master's Theorem Statement (standard)

For $T(n)=aT(n/b)+f(n)$, $a≥1$, $b>1$, $c=\log_b a$:

• Case1 $f(n)=O(n^{c-ε}) → Θ(n^c)$
• Case2 $f(n)=Θ(n^c\log^k n)→Θ(n^c\log^{k+1}n)$
• Case3 $f(n)=Ω(n^{c+ε})$ + regularity → Θ(f)
  (Requires $n/b$ form, not $n^{1/2}$.)

Can Master Apply to $T(n)=2T(\sqrt n)+\log n$?

Not directly — argument is $n^{1/2}$, not $n/b$ with constant $b$. Standard master not applicable. Use substitution / change of variable.

Solution via Domain Transformation

Let $n=2^m$ (assuming $n$ is power of 2 for asymptotics), define $S(m)=T(2^m)$.
Then:
$$S(m)=T(2^m)=2T((2^m)^{1/2})+\log(2^m)=2T(2^{m/2})+m =2S(m/2)+m$$
Now $S(m)=2S(m/2)+m$ → This is master form with $a=2$, $b=2$, $f(m)=m$.

• $c=\log_2 2=1$, $f(m)=m=Θ(m^1)=Θ(m^c)$ → Case2 → $S(m)=Θ(m\log m)$.

Convert back: $m=\log n$ →
$$T(n)=S(\log n)=Θ(\log n · \log \log n)$$

Result: $$T(n)=Θ(\log n \cdot \log\log n)$$
Alternatively $O(\log n \log\log n)$.

Verification via Recursion Tree

Depth: each level halves $m$ → $\log m$ levels = $\log\log n$ levels; work per level $Θ(m)$ → total $Θ(m\log m)$.