a) Calculate the number of times the following loop executes. for 1 to 2n for j=i+1...

   

Transcribed Image Text:

a) Calculate the number of times the following loop executes. for 1 to 2n for j=i+1 to 2n-1 //do something without branching next j next i (3 marks) b) Assuming that n is the input size and that "do something without branching" in the innermost loop of part a) involves 100 calculations, state the order of complexity of the entire calculation using big O notation. c) Another algorithm executes 2n log n + 3 calculations for an input of size n. (i) Is this algorithm O(n)? (11) State the complexity of the algorithm using big omega notation. (3 marks) a) Calculate the number of times the following loop executes. for 1 to 2n for j=i+1 to 2n-1 //do something without branching next j next i (3 marks) b) Assuming that n is the input size and that "do something without branching" in the innermost loop of part a) involves 100 calculations, state the order of complexity of the entire calculation using big O notation. c) Another algorithm executes 2n log n + 3 calculations for an input of size n. (i) Is this algorithm O(n)? (11) State the complexity of the algorithm using big omega notation. (3 marks)