Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability (resit) / 3 / a

Table of contents
- i a
  - Solution i
- ii a
  - Solution ii

i

Solution

Because

T

is positive, the definition of big O notation becomes

\exists C > 0 \exists n_{0} \in N_{+} \forall n \geq n_{0} : T (n) \leq C n^{2} .

Here

C

and

n_{0}

are fixed independently of

n

.

ii

Solution

We prove the stronger bound

T (n) \leq 2 n^{2}

for every

n \geq 1

by strong induction. The initial case is

T (1) = 1 \leq 2

. For

n \geq 2

, put

m = ⌊ n /2 ⌋

. Then

1 \leq m < n

, so the induction hypothesis and the defining recurrence relation give

T (n) = 2 T (m) + n^{2} \leq 4 m^{2} + n^{2} \leq 4 (n /2)^{2} + n^{2} = 2 n^{2} .

Thus

T (n) \leq 2 n^{2} (n \geq 1), T (n) = O (n^{2}) .

The recurrence relation must be read as applying for

n \geq 2

; applying it at

n = 1

would invoke

T (0)

outside the printed domain. No value of

T (0)

is needed.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version