All Questions
3,241
questions
-1
votes
0
answers
41
views
What is the time complexity of list1==list2 operation in Python? [duplicate]
It was my understanding that a condition equating operation would always be O(1) as we are simply checking if LHS is same as RHS.
But this scenario got me thinking.
if list1 == list2:
print("Hi&...
- 17
0
votes
4
answers
97
views
Why is multiplication of integer O(n^2)?
I was wondering why multiplication of integers is O(n^2)? I've been taught addition and multiplication is considered 1 operation. Hence if I multiply an integer of n-digits with another integer of n-...
- 9
-1
votes
1
answer
147
views
Recurrence formula for Divide and Conquer algorithms - wrong?
I'm currently studying recurrences for divide and conquer algorithms (CLRS chapter 4) and I am struggling to understand a slight change that was made to the latest (4th) edition of the book.
The ...
- 1
0
votes
1
answer
65
views
What's the difference between O(n) and O(n+n^1/2) in algorithm?
I watched an online course which mentioned that O(n) and O(n + n^(1/2)) are equivalent in algorithms.
I'm curious about why the n^(1/2) part can be ignored. What is the reason for this omission? I ...
- 25
0
votes
1
answer
61
views
Understanding the Time Complexity Difference of Two Ways to Generate Subsets
I was recently performing a complexity analysis on two separate methods for generating the subsets of a given set. For this question, I am removing all unessential components of the code, meaning that ...
- 247
3
votes
1
answer
110
views
How can I reduce the time complexity of the solution my subset optimization problem?
I have a list of tuples (a, b) of two unrelated positive integers. I am trying to create another list based off of this that maximizes the sum of a, while staying above a threshold.
I also have two ...
- 133
-1
votes
1
answer
106
views
Time complexity of N Queens bruteforce algorithm
I'm solving Big O runtimes but do not feel as though I understand the problem thoroughly enough to answer on my own.
I need to calculate the Big-O runtime for this queens 'bruteforce' function, but I'...
- 29
0
votes
0
answers
60
views
Is there any difference between the terms asymptotic analysis and complexity analysis?
I've read some articles about algorithms analysis and sometimes they seem to use two terms interchangeably and sometimes there seems to be a subtle difference. So I'd like to know about it explicitly, ...
- 63
-1
votes
2
answers
92
views
Which runtime should be faster?
I implemented two solutions to Leetcode problem 988: one that creates a list of strings and sorts it to return the smallest (lexicographically) and another that just keeps track of the smallest ...
- 19
0
votes
2
answers
79
views
What is the runtime of this function and why?
There are many similar questions to this, but I haven't seen this variation.
void myFunc(int n) {
int sum;
int i, j;
sum = 0;
for(i = 1; i <= n; i += 1) {
for(j = 1; j <= ...
- 234
1
vote
1
answer
65
views
What is the average and worst-case time complexity of my string searching algorithm?
I created this algorithm to return the index of the first occurrence of a needle in a haystack, or -1 if the needle is not part of the haystack. It passed on LeetCode with a lower-bound of one and an ...
- 33
0
votes
1
answer
39
views
Complexity in Union of disjointed sets with lists
I can't understand why the complexity of a weighted-union of disjointed sets with lists has complexity O(log n) for one Union and O(nlogn) for n unions.
I know that the complexity is based uppon the ...
0
votes
1
answer
54
views
How to find big o of dependent loops and recursive functions?
I want to be able to measure any code snippet time complexity. Is there a general rule or step by step approach to measure any big o (besides dominant term, removing constants and factors)? What math ...
- 25
0
votes
1
answer
90
views
calculating number of operations in algorithm
total1 = 0
total2 = 0
n = int( input (' Enter the value of n : '))
for x in range(n+1):
total1 += x
for y in range(1 , n):
total2 += total1*y
print('total1' , total1)
print('total2' , ...
- 681
0
votes
1
answer
103
views
Write code to match a specific Big-O-Notation
Our class was challenged by a professor at uni that if we were able to find a algorithm that fittingly describes the following Big-O-Notation, we'd instantly pass his class. I wanted to ask if any of ...
- 1