What is the analysis of my recursive Big-O function?

Question

Preparing for a technical interview, I solved the problem with a recursive solution.

What is the difficulty of executing a recursive function such as this? I'm more interested in an explanation, not an answer.

From my analysis - the number of operations will be half n. That is, a string of 10 characters will receive 5 function calls in the worst case. But I never saw O (n / 2) runtime. In addition, my analysis eliminates the call of an auxiliary function counterpartOf. Can someone please show me the correct analysis?

Write a function that takes a string of brackets ({}) and returns if it is balanced.

function checkBraces(input){
  // start at the center and work outwards, recursively
  var c = input.length / 2;

  if (input.charAt(c) !== counterpartOf(input.charAt(c-1))) {
    var match = false;
    return match;
  } else {
    // if only 2 characters are left, all braces matched
    if (input.length === 2){
      var match = true;
      return match;
    } else {
      input = input.substring(0,c-1) + input.substring(c+1,input.length);
      return checkBraces(input);
    }
  }
  return match;
}

function counterpartOf(brace){
  closing = ['}', ')', ']'];
  opening = ['{', '(', '['];
  var i = opening.indexOf(brace);
  var counterpart = closing[i];
  return counterpart;
}

Answer 1

, /2, * 2 - .

:

http://en.wikipedia.org/wiki/Big_O_notation#Multiplication_by_a_constant

O (k * g) = O (g), k .

, , . , , , .

push down automata. : http://people.cs.clemson.edu/~goddard/texts/theoryOfComputation/7.pdf

Answer 2

O(n) , javascript substring . substring O(k), k - , O(n^2). javascript substring.

Answer 3

The view is off topic and not sure if you needed to use recursion, but I think there is a much more efficient way to get the result:

function checkBraces( input )
{
   // if the string is an odd number of characters, return immediately.
   if( input.length % 2 !== 0 ) return false; 

   // split the string in half
   var c = input.length / 2;
   var r = input.substr( c );
   var l = input.substr( 0, c );

   // take the left side, reverse it, and swap each left bracket character with it counterpart
   l = l.split('').reverse().join('').replace(/\{|\(|\[/g, counterpartOf );

   // strings should match
   return r == l;
}