Time complexity and induction problems

[darkvalentine]

Homework Statement

1. HOARE-PARTITION(A,p,r) rearrange the array A[p...r] into 2 (possibly empty) subarray A[p...q] and A[q+1...r], so that each element of A[p...q] is at most A[p], and each element of A[q+1...r] is at least A[p].

x<-A[p]
i<-p-1
j<-r+1
while true
do repeat j<-j-1
until A[j]<=x
repeat i<-i+1
until A>=x
if i<j
then exchange A <-> A[j]
else return j
Find the worst time complexity in term of p and r.2/ Prove by induction on k :
(1+1/n)^k < 1 + k/n + k^2/n^2 for 1<= k <=n

Homework Equations

The Attempt at a Solution

1/ For the first repeat until I got time complexity to be O(r-p), but then I stuck.

2/ For base case it's true, but no clue how to do the inductive case.

 

[mighty2000]

1/ The worst time complexity for the HOARE-PARTITION algorithm is O(r-p) because in the worst case scenario, the while loop will run for r-p times. This is because in each iteration, either i or j will move one step closer to the middle element (q) and they can only move a maximum of r-p times before they reach q.

2/ For the inductive case, assume that the statement is true for k = n-1. Then we have:
(1+1/(n-1))^(n-1) < 1 + (n-1)/(n-1) + (n-1)^2/(n-1)^2
=> (1+1/(n-1))^(n-1) < 1 + 1 + (n-1) = n
Now we need to prove that this statement is also true for k = n. We have:
(1+1/n)^n = ((1+1/(n-1))^(n-1))*(1+1/(n-1))
Using our assumption, we can say that:
(1+1/n)^n < n*(1+1/(n-1)) < n*(1+(n-1)) = n^2
Hence, the statement is true for all values of k between 1 and n.