Linked Questions
42 questions linked to/from How to come up with the runtime of algorithms?
193
votes
3
answers
25k
views
Is there a system behind the magic of algorithm analysis?
There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
- 71.6k
3
votes
2
answers
252
views
Determining Big O [duplicate]
i<--2
while (i<n)
someWork (...)
i <-- power (i,2)
done
Given that someWork(...) is an O(n) algorithm, what is the worst case
...
user3806894
-1
votes
1
answer
151
views
How to get an O(n) for a search algorithm [duplicate]
Given an two sorted arrays X and Y, both of size n. Determine if there is an element x of X and an element y of Y such that x = 3y. The algorithm needs to run in linear time in the worst case.
At the ...
- 129
2
votes
1
answer
114
views
Analysis of Algorithms: Applying Concepts [duplicate]
I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application.
I ...
- 21
1
vote
1
answer
143
views
What exactly is bigO notation? [duplicate]
I've heard of bigO notation but I don't really understand how do I determine it for my code and what exactly does it represent?
I heard that there are two:
RunTime
Memory Complexity
How can I learn ...
- 113
0
votes
0
answers
82
views
How to calculate Complexity Time O()? [duplicate]
Can anybody give me a way that i can use to calculate Complexity Time problems, i mean a way that will work on any complex code whatever it was.
I can solve basic problems, but whenever the problem ...
- 109
100
votes
3
answers
34k
views
How does one know which notation of time complexity analysis to use?
In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.
However, there are ...
- 1,313
4
votes
2
answers
34k
views
Time complexity of a backtrack algorithm
I've developed the following backtrack algorithm, and I'm trying to find out it time complexity.
A set of $K$ integers defines a set of modular distances between all pairs of them. In this
algorithm, ...
- 171
3
votes
2
answers
15k
views
How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?
How are asymptotical time complexities calculated for recursive algorithms?
Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ...
- 129
11
votes
2
answers
687
views
How to prove that $n(\log_3(n))^5 = O(n^{1.2})$?
This a homework question from Udi Manber's book. Any hint would be nice :)
I must show that:
$n(\log_3(n))^5 = O(n^{1.2})$
I tried using Theorem 3.1 of book:
$f(n)^c = O(a^{f(n)})$ (for $c >...
- 113
0
votes
2
answers
2k
views
how to calculate time complexity of non terminating loops
I'm studying about data structures and algorithms in that Time complexity and calculating time complexity of the programs.
I just wondered that how to calculate time complexity of non terminating ...
user48126
0
votes
4
answers
5k
views
Proving Quicksort has a worst case of O(n²)
I am sorting the following list of numbers which is in descending order.
I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$
...
- 649
3
votes
2
answers
6k
views
Using software to calculate the complexity of an algorithm
I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some ...
- 131
3
votes
2
answers
5k
views
What is running time of an algorithm?
What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the ...
- 263
1
vote
2
answers
3k
views
Worst case time complexity of heap sort
I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows:
...
- 111