Докажите для любого a> b> 0, b ^ n в Big-O a ^ n - PullRequest
Новая
       21

Докажите для любого a> b> 0, b ^ n в Big-O a ^ n

0 голосов
/ 15 января 2012

Докажите, что для любых действительных чисел a, b таких, что a> b> 0, b ^ n, есть O (a ^ n), n> = 1.

Я искал несколько принадлежащих мне учебников по дискретной математике, а также несколько онлайн-поисков любых похожих примеров или теорем, связанных с этим доказательством. Я не ищу прямого решения, но, возможно, мне показывают правильные методы или парадигмы для решения доказательства.

1 Ответ

2 голосов
/ 15 января 2012

Если вы имеете в виду 

Prove that for any real numbers, a, b such that a > b > 0, b^n is O(a^n)

Затем подумайте об определении O(a^n)

Из вики , 

1) For f(x), g(x) defined on a subset of reals
2) if there exists some positive **constant** M and real number x_0, such that
3) if ABS(f(x)) <= M * ABS(g(x)) for all x > x_0

В данном случае f(x) = b^x и g(x) = a^x. Я собираюсь рассматривать этот вопрос, как будто это домашнее задание, даже если он не помечен как один ... поправьте меня, если я ошибаюсь!

Подумайте о подключении функции к шагам (особенно 3) и посмотрите, сможете ли вы найти любую пару x_0, M, для которой это верно. Удачи!

EDIT Я изменил f(x) = b^n и g(x) = a^n на f(x) = b^x и g(x) = a^x

РЕДАКТИРОВАТЬ - СОВЕТ

Шаг 3) можно интерпретировать как: 

ABS(f(x)) / ABS(g(x)) <= M for all x > x_0

Выберите вашу любимую константу M и посмотрите, сможете ли вы найти x_0, который работает for all x.

...