Recent content by Chinta

Actually I've got this answer that the question was wrong right after I posted the problem here a long time ago...I myself figured it out but forgot to post it here. :D Anyway thanks for your solution too. I got this question from a graph theory tutorial in internet actually.

Kruskal's Algorithm can be used here as follows: If edge costs are all distinct then running Kruskal's Algorithm on this graph G(say) creates only a unique sequence of (n-1) edges with edge costs in increasing order. Hence G has a unique minimum spanning tree.

The problem is as follows: --------------------------------------------------------------------------------------------------------------------------------- Let G be a connected graph. For a vertex x of G we denote by G−x the graph formed by removing x and all edges incident on x from G. G is...

Many thanks...I had a wrong concept about this thing. You made it clear. (Whew)

So is k a constant at all or a linear function of n?

I am not concerned about the inductive proof. All I want to know is that whether the constant "k" will be there or not? Because there are (n-1) additions being performed for the statement 1 + CN(node->left) + CN(node->right) and assuming each addition takes "c" unit time then we are getting...

[FONT=comic sans ms]As you said that let's assume this as a binary tree, then we have a=(n/2) and (n-a-1)=(n/2)-1. Then T(n) can be written as follows: T(n)=T(n/2) + T{(n/2) -1} + k =2*T(n/2) + k as a result of which T(n) [FONT=comic sans ms]∈ O(n) .[FONT=comic sans ms]...

I guess this is the first question on partly CS topic in this forum. But I think you guys will be able to help me. I have an algorithm which goes as follows: int CN(struct node *node) { if(node==null) return 0; return 1 + CN(node->left) +...