Question 7: Algorithms and Their Complexity a) Write a simple program in pseudoc

Question

Question 7: Algorithms and Their Complexity

a) Write a simple program in pseudocode (or in Python, C, C++, or Java, but only use basic commands so that comparisons can be counted) that receives a sequence of integers a1, …, an as its input and determines if the sequence contains two distinct terms x, y such that x = y2 . Once it finds such terms, it prints them and terminates; it does not continue searching after the first find. If the program does not find any such terms, it prints a disappointed comment and also terminates.

b) Describe the kind of input that causes worst-case time complexity for your algorithm (only count comparisons), and explain why this is the case.

c) Provide an equation for your algorithm that describes the number of required comparisons as a function of input length n in the worst case. For some algorithms, it may be a good idea to first use a sum notation, but at the end you should provide a closed-form equation, i.e., one that no longer uses the sum symbol but only operations such as multiplication or addition of individual numbers or variables.

d) Use the big-O-notation to describe the worst-case time complexity of your algorithm.

Explanation / Answer

Answer to (b): The worst-case time complexity (in terms of number of comparisons) occurs when a number and its square are the last two numbers on the sequence. For example, let's consider 1, 2, 3, 4.

When input is [1, 2, 3, 4], No. of comparisons = 5.

When input is [1, 3, 2, 4] or [1, 3, 4, 2], No. of comparisons = 9.

Answer to (c): As is clear from the above example, the number of comparisons with this sorting technique is related to the input lenght in the following way:

C = (n-1)2   where, C = no. of comparisons, n = input length

Anser to (d): The big-O-notation in terms of number of comparisons can be given as O(N2).

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.