What is is the time complexity for the following function in Python? The function takes two inputs, string1 and string2, concatenates them together using “+” and returns the concatenated string. is it O(n + m) where n is the length of string1 and m is the length of string2? thanks! Answer Yes, it …
Tag: time-complexity
What is the time complexity of a bubble sort algorithm applied n times to the same array?
I had this question on a test and i’m trying to understand it: What is the time complexity of this function (in the worst case) assuming that Bubblesort() is the most optimized version of the Bubble Sort algorithm? The options were: Linear Quadratic Cubic I was thinking that the first sort (because it&#…
Power Plant – solve the problem in O(nlogn)
I had the following problem on the exam: A certain power plant needs coal to operate, so it has ordered n deliveries, and information about each delivery (number of tons) is stored in a list A. The delivered coal is stored in warehouses with consecutive numbers 0, 1, …. (Their exact number is not given)…
Algorithm for ordering data so that neighbor elements are as identical as possible
I have a (potentially large) list data of 3-tuples of small non-negative integers, like I want to order the tuples within data so that neighboring tuples (data[i] and data[i+1]) are “as similar as possible”. Define the dissimilarity of two 3-tuples as the number of elements which are unequal betwe…
What is the complexity of str() function in Python3?
I have to create a function respecting an O(n) complexity and to do that i want to use the str() function. Can someone explain me if : Is this code O(1) or O(4) because of the 1+0+0+0 ? Answer As can be seen from the source code, the implementation of int.__str__ has runtime complexity of O(m*n) where m is th…
What is the complexity of this algorithm and is there a possibility to improve it?
This is the algorithm of this problem: Write a function that takes two arrays as input, each array contains a list of A-Z; your program should return True if the 2nd array is a subset of 1st array, or False if not. Answer The complexity of your algorithm is O(n*k), where n and k is length of arrays. You have
What is the Time Complexity of this code sample? like nested loop, but inner loop is a fixed number
m, n are two python array inner loop is maximum 3 Thinking O(n)? because inner looping is in a fixed amount O(n*m)? O(n*3)? this is not the correct way :( What is the correct O time complexity for this? Answer Time complexity of the statement inside the inner loop is in O(1). Because, it is just only one comp…
What will the time complexity of this python program in Big O notation?
I find it difficult to calculate the time complexity of this program as it involves a lot of built-in methods. Could anyone please help? Basically the question is to find topper of each subject and 3 overall best performers! Input csv file looks something like this: Output: Answer Your for loop goes over all …
With lowest possible time complexity , subtract every number in a list from the first lower number after it
I have a list of numbers and I want to subtract every number from the smaller value after it but with the lowest possible complexity I have the list [7, 18 ,5 ,5 ,20 ,9 ,14 ,7 ,19] The first lower value after 7 is 5 so it will subtract 7 from 5, the same for 18 the first lower
How to calculate time complexity of these two functions? (recursion)
The first function: The second function: Now I can see why both of the function’s space complexity is O(n) since the recursion depth is equal to n. But about time complexity, I’m not being able to calculate it like I used to do with the equation for normal recursion, lets say instead of f(f(n-1)) …