Analzying the following code and answer the complexity of this algorithm

public String getString()
String s= "";
for(int i =0 ; i

Question

Analzying the following code and answer the complexity of this algorithm

public String getString() 
String s= "";
for(int i =0 ; i < LARGE_NUMBER ; i++) {
s += "a";
}
return s;
}

Sigiloso · Accepted Answer

IAM CONFUSED???? THE COMPLEXITY SHOULD BE O(N)

Sigiloso · Answer

Well I started with that too but the interviewer eventually gave me answer in order of 3 and 4. I have told him that string copying (append operation) will make it n2. Then he went into details about what will happen during memory allocation. What will the graph look like when you are just about to throw OOME. And he said that it will lead to n3 or n4. I have read some many algorithm and O(n) and have never seen anyone talking about memory allocation and including that in your complexity calculation...

Sigiloso · Answer

O(n) if you only consider the above loop. If you consider string appending then it becomes n(n-1)/2 i.e n2 (O(n2) [ n square]

Zynga

Pergunta de entrevista da empresa Zynga

Respostas da entrevista

Empresas seguidas

Buscas de vagas