Data structures

Vaishnavi01 asked Sep 28, 2018

328 views

0 votes

A 3-ary tree is a tree in which every internal node has exactly 3 children. Use induction to prove that the number of leaves in a 3-ary tree with n interval nodes is 2(n-1)+3.

Vaishnavi01 asked Sep 28, 2018

Vaishnavi01

328 views

See all

2 2 Comments

Shaik Masthan

commented Sep 28, 2018

@Vaishnavi01

did you want just proof or especially Induction proof?

if you want especially induction proof, but why ? ( i mean in GATE, they didn't ask descriptive questions )

0 votes

Magma

commented Sep 28, 2018

but correct answer is : $\frac{2 n + 1}{3}$

0 votes

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Voting & Accepting an answer helps improve the community

← Previous Next →

← Previous in category Next in category →

Related questions

9 votes

2 answers

GO Classes asked May 4, 2022

512 views

GO Classes Weekly Quiz 9 | Data Structures | Linked List | Question: 8
If $f(n) = O(g(n))$ and $f(n) = \Omega(g(n)),$ then it is always true that $f(n) = o(g(n)).$ $f(n) = \theta(g(n)).$ $f(n) = \omega(g(n)).$ both A and B are always true.

If $f(n) = O(g(n))$ and $f(n) = \Omega(g(n)),$ then it is always true that$f(n) = o(g(n)).$$f(n) = \theta(g(n)).$$f(n) = \omega(g(n)).$both A and B are always true.

GO Classes

512 views

GO Classes asked May 4, 2022

Programming in C
goclasses_wq9
goclasses
algorithms
asymptotic-notation
1-mark

+ –

5 votes

2 answers

GO Classes asked May 4, 2022

569 views

GO Classes Weekly Quiz 9 | Data Structures | Linked List | Question: 12
Which of the following statement(s) is/are true? If $\text{T1}(x) = \text{O}(f(x))$ and $\text{T2}(x) = \text{O}(g(x))$ then $\text{T1}(x) + \text{T2}(x) = \text{O} (\max(f(x), g(x))$ If $\text{T}(x) = \text{O}(cf(x)),$ ... then $\text{T1}(x) \ast \text{T2}(x) = \text{O}(f(x) \ast g(x))$ $2^{(n+1)} = \text{O}(2^{n} ).$

Which of the following statement(s) is/are true?If $\text{T1}(x) = \text{O}(f(x))$ and $\text{T2}(x) = \text{O}(g(x))$ then $\text{T1}(x) + \text{T2}(x) = \text{O} (\max(...

GO Classes

569 views

GO Classes asked May 4, 2022

Programming in C
goclasses_wq9
goclasses
algorithms
asymptotic-notation
multiple-selects
2-marks

+ –

7 votes

2 answers

GO Classes asked May 4, 2022

1,560 views

GO Classes Weekly Quiz 9 | Data Structures | Linked List | Question: 13
Consider two statements below - $\text{S1}:$ For all positive $f(n), f(n) + o(f(n)) = \theta(f(n)).$ $\text{S2}:$ For all positive $f(n), g(n)$ and $h(n),$ if $f(n) = O(g(n))$ ... $\text{S1}$ is True but $\text{S2}$ is False. $\text{S2}$ is True but $\text{S1}$ is False. Both are True. Both are False.

Consider two statements below -$\text{S1}:$ For all positive $f(n), f(n) + o(f(n)) = \theta(f(n)).$$\text{S2}:$ For all positive $f(n), g(n)$ and $h(n),$ if $f(n) = O(g(n...

GO Classes

1.6k views

GO Classes asked May 4, 2022

Programming in C
goclasses_wq9
goclasses
algorithms
asymptotic-notation
2-marks

+ –

7 votes

2 answers

GO Classes asked May 4, 2022

867 views

GO Classes Weekly Quiz 9 | Data Structures | Linked List | Question: 14
Which of the following(s) is/are true? If $f(n) = O(n^2)$ then $f(n) = O(n).$ If $f(n)$ is $O(3^{\log_{10}n}),$ then $f(n)$ is $O(n^2).$ The function $f(n) = \lg(n!) = O(n \lg n).$ Growth of the sum $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ can be described by $\theta(\log n).$

Which of the following(s) is/are true?If $f(n) = O(n^2)$ then $f(n) = O(n).$If $f(n)$ is $O(3^{\log_{10}n}),$ then $f(n)$ is $O(n^2).$The function $f(n) = \lg(n!) = O(n \...

GO Classes

867 views

GO Classes asked May 4, 2022

Programming in C
goclasses_wq9
goclasses
algorithms
asymptotic-notation
multiple-selects
2-marks

+ –

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

2 2 Comments reply

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Related questions

2 2 Comments