Использование математической индукции для доказательства рекуррентной системы

Question

Имея fnc:

bool ISINTREE( int x, BinTree<int> t) 
  {
  bool  b = false

  if  (!t.isEmpty())
    {
    if  (x  ==  t.getRoot())
      { b = true }
    else
      {
      if (ISINTREE(x,t.leftTree()))
        { b = true }
      if (ISINTREE(x,t.rightTree()))
        { b = true }
      }
    }

  return  b 
  } 

Как доказать (используя математическую индукцию), что T (n) = 11 × 2 ^ n - 7 является решением система повторения для этого fnc.

* 1007 EDITED ** * 1008 Пусть F (n) = 11 * 2 ^ n - 7
Теперь,
для k> 0
T (k-1) = F (k-1) = 11 * 2 ^ (k-1) -7
T (k) = 7 + 2 * (T (k-1))
= 7 + 2 * (11 * 2 ^ (к-1) -7)
= 11 * 2 ^ k -7

Answer 1

Что здесь n? Количество элементов в дереве? Если это так, то, конечно, мы можем сказать, что в худшем случае этот алгоритм посещает каждый узел дерева, поэтому время выполнения в худшем случае T(n) = n, и в этом случае предпосылка (что это T(n) = 11 . 2^n - 7) ) не может быть действительным.

UPDATE

Чтобы удовлетворить недоверчивость, давайте взглянем на худший сценарий (предмет для поиска отсутствует в дереве). Без ограничения общности давайте предположим, что мы смотрим на идеально сбалансированное дерево, то есть каждое поддерево имеет (n-1)/2 элементов. Следовательно, при этих допущениях рекуррентное соотношение:

T(n) = 2.T((n-1)/2) + 7

(я бы сказал, что здесь действительно только 4 исполняемые операции, но давайте для простоты назовем их 7).

Очевидно, что T(n) = 11 . 2^n - 7 не является решением для этих отношений.