Last update: Thu Apr 12 03:37:15 MDT 2012
Top |
Symbols |
Numbers |
Math |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z
BibTeX entry
@Article{Nilsen:1995:WET,
author = "Kelvin D. Nilsen and Bernt Rygg",
title = "Worst-case execution time analysis on modern
processors",
journal = j-SIGPLAN,
volume = "30",
number = "11",
pages = "20--30",
month = nov,
year = "1995",
CODEN = "SINODQ",
ISSN = "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
ISSN-L = "0362-1340",
bibdate = "Tue May 4 05:55:46 MDT 1999",
bibsource = "http://www.acm.org/pubs/toc/",
URL = "http://www.acm.org:80/pubs/citations/proceedings/plan/216636/p20-nilsen/",
abstract = "Many of the trends that have dominated recent
evolution and advancement within the computer
architecture community have complicated the analysis of
task execution times. Most of the difficulties result
from two particular emphases: instruction-level
parallelism; and optimization of average-case behavior
rather than worst-case latencies. Both of these trends
have resulted in increased nondeterminism in the time
required to execute particular code sequences. Since
the analysis required to determine worst-case task
execution times on modern processors is so complicated,
it is not practical for programmers to perform all of
the necessary analyses by hand. Tools must aid them.
This paper describes ongoing research on a collection
of tools intended to automate the analyses that must be
performed in order to build reliable real-time software
for modern computing environments. Emphasis is given to
the interplay between components of the development
environment.",
acknowledgement = ack-nhfb,
affiliation = "Dept. of Comput. Sci., Iowa State Univ., Ames, IA,
USA",
classification = "C5470 (Performance evaluation and testing); C6110B
(Software engineering techniques); C6150G (Diagnostic,
testing, debugging and evaluating systems)",
confname = "LCT-RTS '95. Proceedings of the ACM SIGPLAN 1995
workshop on Languages, compilers, \& tools for
real-time systems, June 21--22, 1995, La Jolla,
California",
keywords = "Average-case behavior; Computer architecture; design;
Instruction-level parallelism; measurement; Modern
processors; Nondeterminism; Optimization; performance;
Reliable real-time software; Software development
environment; Software engineering; System analysis;
Task execution times; theory; Worst-case execution time
analysis; Worst-case latencies",
subject = "{\bf D.4.1} Software, OPERATING SYSTEMS, Process
Management. {\bf C.4} Computer Systems Organization,
PERFORMANCE OF SYSTEMS.",
thesaurus = "Program diagnostics; Programming environments;
Real-time systems; Software performance evaluation;
Software reliability",
}
Related entries
- aid,
25(6)78,
25(6)197,
25(6)223,
25(6)246,
26(6)107,
26(6)229,
26(6)317,
26(12)175,
27(7)1,
27(7)12,
27(7)22,
27(7)32,
27(9)200,
28(6)1,
28(6)13,
28(6)26,
28(6)46,
30(3)94,
31(5)23,
31(9)116
- analyse,
26(6)80,
26(6)80-1,
27(7)106,
27(7)224,
28(6)68,
28(6)78-1,
28(6)268,
28(7)33,
29(6)1,
29(6)147,
29(6)242,
29(6)242-1,
29(6)266,
29(11)286,
30(6)13,
30(6)196,
30(11)70,
32(8)38,
33(7)43
- automate,
25(6)102,
30(11)60
- behavior,
6(4)111,
6(4)159,
25(6)234,
26(6)59,
27(7)1,
27(7)12,
27(7)32,
27(7)55,
27(7)116,
28(3)69,
28(3)367,
28(3)369,
28(6)100,
28(7)44,
28(10)326,
28(10)326-1,
29(6)73,
29(11)61,
29(11)132-1,
29(11)145,
29(11)328,
30(3)35,
30(6)1,
30(6)67,
30(6)79-1,
30(8)68,
30(11)50,
30(11)70,
30(11)125,
32(10)1,
32(10)108,
33(7)27,
33(7)83,
33(11)12,
33(11)240,
34(7)35
- both,
25(1)59,
25(6)9,
25(6)85-1,
25(6)102,
25(6)112,
26(4)28,
26(7)83,
27(5)z,
27(7)82,
27(7)94,
27(7)175,
27(7)212,
27(7)249,
27(7)283,
27(10)452,
28(3)231,
28(3)299,
28(3)353,
28(3)357,
28(6)26,
28(6)177,
28(6)248,
28(7)13,
28(7)23,
28(7)54-1,
28(7)112,
28(7)129,
29(6)1,
29(6)290,
29(6)302,
29(8)59,
29(8)119,
29(11)2,
29(11)38,
29(11)61,
29(11)98,
29(11)110,
29(11)122,
29(11)171,
29(11)183,
29(11)252,
29(11)274,
29(11)308,
30(2)25,
30(3)50,
30(6)56,
30(6)67,
30(6)93,
30(6)130,
30(6)186,
30(6)205,
30(6)279,
30(8)29,
30(8)68,
30(8)102,
30(8)156,
30(8)179,
30(8)207,
31(5)108
- build,
25(4)51,
27(7)82,
27(9)262,
29(6)196,
29(11)98,
30(3)94,
30(3)111,
30(8)29,
30(8)80-1,
34(4)19,
34(4)19-1,
34(9)249
- C.4,
27(9)76,
27(9)111,
27(9)124,
27(9)137,
27(9)162,
27(9)175,
27(9)187,
27(9)248,
27(9)262,
27(9)274,
29(6)186,
29(11)51,
29(11)61,
29(11)98,
29(11)110,
29(11)122,
29(11)183,
29(11)219,
29(11)232,
29(11)242,
29(11)252,
29(11)274,
29(11)308,
29(11)319,
29(11)328,
30(11)31,
30(11)60,
30(11)70,
30(11)79,
31(9)2-1,
31(9)138,
31(9)160,
31(9)258,
31(9)268,
33(11)71,
33(11)92,
33(11)105,
33(11)170,
33(11)181,
33(11)193,
33(11)205,
33(11)228,
33(11)240,
33(11)272,
33(11)283,
33(11)295
- C5470,
26(4)28,
26(4)290,
29(11)76-1,
29(11)122,
29(11)132-1,
29(11)145,
29(11)158,
29(11)196,
29(11)219,
29(11)274,
29(12)87
- C6110B,
25(10)237,
27(12)20,
28(2)21,
28(6)166,
28(7)112,
29(1)27,
29(4)23,
29(4)41,
29(5)7,
29(6)302,
29(7)29,
29(7)43,
29(8)35,
29(8)46,
29(8)59,
29(8)84,
29(8)111,
29(9)77,
29(10)176,
29(10)205,
29(10)212,
29(12)78,
30(2)12,
30(3)103,
30(3)111,
30(6)103,
30(6)291,
30(8)11,
30(8)19,
30(8)29,
30(8)80-1,
30(11)31,
30(11)60,
30(11)134,
30(11)146-1
- C6150G,
25(12)85,
28(6)1,
28(6)13,
28(6)26,
28(6)46,
28(6)177,
28(7)44,
28(12)169,
29(1)37,
29(4)15,
29(6)1,
29(6)171,
29(6)196,
29(6)242,
29(6)278,
29(6)290,
29(6)302,
29(6)313,
29(9)140,
29(10)403,
29(11)122,
29(11)232,
29(12)38,
29(12)73,
30(3)1,
30(3)50,
30(3)62,
30(3)94,
30(6)67,
30(6)79-1,
30(6)93,
30(6)218,
30(6)233,
30(6)258,
30(6)270,
30(6)291,
30(8)11,
30(11)79,
30(11)88,
30(11)99,
30(11)117
- case, Worst-,
28(6)166,
28(7)129,
30(11)1,
30(11)20
- case, worst-,
28(6)166,
28(7)129,
29(11)76-1,
30(11)1
- community,
28(3)69,
28(3)299,
28(3)355,
29(3)18,
30(6)291
- complicated,
27(7)331,
27(9)248,
28(3)349,
29(6)121,
29(6)135,
30(11)134
- component,
6(4)196,
25(6)234,
25(10)1,
26(1)99,
26(9)297,
27(7)82,
27(7)224,
28(3)299,
28(6)100,
28(8)46,
29(6)206,
29(8)35,
29(8)46,
29(10)212,
29(10)272,
29(11)145,
29(11)158,
29(12)58,
30(3)103,
30(8)123,
30(11)31,
30(11)146-1,
31(10)359,
31(10)444,
31(10)444,
32(10)206,
33(7)1,
33(7)43,
33(10)97,
33(10)97-1,
34(10)399
- D.4.1,
27(9)38,
27(9)51,
27(9)162,
27(9)223,
27(9)238,
27(9)262,
29(11)12,
29(11)25,
29(11)183,
30(11)7,
30(11)50,
30(11)79,
31(5)79,
32(5)71,
33(11)24,
33(11)46,
33(11)58,
33(11)127,
33(11)262,
33(11)272,
34(3)166
- determine,
25(6)92,
25(6)112,
25(6)223,
25(6)311,
27(7)116,
27(7)283,
28(6)26,
28(6)56,
28(6)126,
29(6)85,
29(6)121,
29(6)278,
30(6)56,
30(6)93,
30(6)218,
30(11)70,
30(11)79
- Diagnostic,
25(12)85,
28(6)1,
28(6)13,
28(6)26,
28(6)46,
28(6)177,
28(7)44,
28(12)169,
29(1)37,
29(4)15,
29(6)1,
29(6)171,
29(6)196,
29(6)242,
29(6)278,
29(6)290,
29(6)302,
29(6)313,
29(9)140,
29(10)65,
29(10)403,
29(11)122,
29(11)232,
29(12)38,
29(12)73,
30(3)1,
30(3)50,
30(3)62,
30(3)94,
30(6)67,
30(6)79-1,
30(6)93,
30(6)218,
30(6)233,
30(6)258,
30(6)270,
30(6)291,
30(8)11,
30(11)79,
30(11)88,
30(11)99,
30(11)117,
31(5)249
- difficulty,
29(6)278,
29(8)101,
29(11)219,
30(3)94,
30(3)103
- dominated,
30(6)47
- emphasis,
25(6)1,
28(3)209,
28(3)271,
29(11)219,
29(11)242
- engineering,
6(4)72,
25(8)15,
25(10)237,
26(10)73,
27(10)166,
27(10)166-1,
27(12)20,
28(2)21,
28(3)343,
28(6)166,
28(7)1,
28(7)112,
28(8)90,
29(1)27,
29(4)23,
29(4)41,
29(5)7,
29(6)196,
29(6)302,
29(7)29,
29(7)43,
29(8)35,
29(8)46,
29(8)59,
29(8)84,
29(8)111,
29(9)77,
29(10)176,
29(10)205,
29(10)212,
29(11)132-1,
29(12)78,
30(2)12,
30(3)103,
30(3)111,
30(6)103,
30(6)291,
30(8)11,
30(8)19,
30(8)29,
30(8)48,
30(8)80-1,
30(10)333,
30(11)31,
30(11)60,
30(11)79,
30(11)134,
30(11)146-1,
32(1)86,
32(1)86-1,
32(5)159,
33(7)1,
33(7)11,
33(7)19,
33(7)27,
33(7)35,
33(7)43,
33(7)51,
33(7)59,
33(7)67,
33(7)75,
33(7)83,
33(12)14,
34(10)97
- environment,
25(2)25,
25(4)20,
25(6)78,
25(6)189,
25(6)209,
25(9)39,
25(11)85,
26(7)114,
26(11)62,
27(7)12,
27(7)44,
27(11)27,
28(1)44,
28(2)53,
28(3)69,
28(3)201,
28(3)299,
28(4)21,
28(6)26,
28(7)64,
28(10)215,
29(6)13,
29(6)36,
29(10)51,
29(10)85,
29(10)212,
29(10)229,
29(10)355,
29(11)308,
29(12)73,
30(3)111,
30(8)48,
30(11)146-1,
31(8)64,
31(8)64-1,
31(9)258,
32(3)42,
32(9)57,
32(9)57-1,
33(7)59,
34(10)340,
34(12)37
- environments,
25(6)197,
25(6)197-1,
25(10)269,
26(12)184,
27(7)12,
27(7)55,
27(11)90,
28(3)271,
28(3)345,
28(12)169,
29(8)101,
29(8)119,
29(9)44,
29(9)77,
29(10)205,
29(10)229,
29(10)355,
29(10)403,
29(11)145,
29(11)308,
29(11)319,
30(3)111,
30(4)7,
30(7)2,
30(11)117,
31(5)23,
31(6)251,
32(5)31
- evaluating,
25(12)85,
28(6)1,
28(6)13,
28(6)26,
28(6)46,
28(6)177,
28(7)44,
28(12)169,
29(1)37,
29(4)15,
29(6)1,
29(6)171,
29(6)196,
29(6)242,
29(6)278,
29(6)290,
29(6)302,
29(6)313,
29(9)140,
29(10)65,
29(10)403,
29(11)122,
29(11)232,
29(12)38,
29(12)73,
30(3)1,
30(3)50,
30(3)62,
30(3)94,
30(6)23,
30(6)67,
30(6)79-1,
30(6)93,
30(6)218,
30(6)233,
30(6)258,
30(6)270,
30(6)291,
30(8)11,
30(8)189,
30(11)79,
30(11)88,
30(11)99,
30(11)117,
34(11)2
- evolution,
6(4)180,
25(3)60,
25(10)67,
28(3)177,
28(3)201,
28(3)231,
28(3)271,
29(8)119,
29(11)122,
31(10)268,
31(12)22,
32(10)1,
32(10)1-1,
33(6)48,
33(12)72,
34(2)1,
34(2)41,
34(10)415
- execute,
25(6)174,
26(4)132,
26(4)290,
27(7)44,
27(9)223,
30(6)218,
30(6)246,
30(8)217
- given,
25(6)28,
25(6)246,
25(6)322,
27(7)55,
27(7)188-1,
27(7)249,
28(3)149,
28(3)345,
28(3)365,
28(6)26,
28(6)126,
28(7)54-1,
28(7)102,
28(7)119,
29(6)36,
29(6)121,
29(11)308,
30(4)13,
30(6)79-1,
30(6)186,
30(11)50,
30(11)88,
34(5)z,
34(5)z-1
- hand,
25(6)112,
25(6)311,
27(9)285,
28(3)347,
33(7)59
- increased,
25(6)66,
26(4)28,
28(6)177,
29(6)1,
29(6)97,
29(11)2,
29(11)274,
29(11)319
- instruction-level,
27(9)248,
30(6)151,
30(11)41
- intended,
27(7)128,
28(7)112,
29(6)206,
30(8)11
- latency,
27(9)51,
28(6)278,
28(7)218,
29(6)107,
29(11)2,
29(11)86,
29(11)98,
29(11)219,
29(11)274,
29(11)308,
29(11)328,
30(6)130,
30(6)151,
30(8)48,
31(9)198,
31(9)258
- level, Instruction-,
30(6)151
- level, instruction-,
27(9)248,
30(6)151
- many,
25(1)59,
25(6)112,
25(6)137,
25(6)189,
25(6)283,
27(1)95,
27(5)z,
27(7)68,
27(7)82,
27(7)116,
27(7)188-1,
27(9)285,
28(3)69,
28(3)343,
28(3)345,
28(3)347,
28(6)100,
28(6)187,
28(6)237,
28(6)258,
28(6)300,
28(7)13,
28(7)33,
28(7)54-1,
29(6)1,
29(6)36,
29(6)49,
29(6)73,
29(6)85,
29(6)171,
29(6)206,
29(6)302,
29(8)94,
29(8)101,
29(11)145,
29(11)171,
29(11)196,
29(11)219,
29(11)252,
29(11)328,
30(3)13,
30(3)94,
30(3)119,
30(6)1,
30(6)67,
30(6)103,
30(6)291,
30(8)68,
30(8)134,
30(8)217,
30(11)134,
33(7)19,
33(7)27
- modern,
27(1)95,
27(7)82,
27(7)273,
28(3)69,
28(6)177,
29(6)36,
29(6)206,
30(8)166,
30(11)20,
30(11)125,
34(9)8
- most,
25(4)73,
25(6)53,
25(6)165,
25(6)189,
25(6)209,
25(6)337,
26(4)290,
27(7)1,
27(7)94,
27(7)152,
27(7)300,
28(3)69,
28(3)333,
28(3)347,
28(6)36,
28(6)90,
28(6)139-1,
28(6)177,
28(6)197,
28(7)13,
28(7)54-1,
28(7)149,
28(7)208,
28(8)90,
29(6)61,
29(6)85,
29(6)107,
29(6)186,
29(8)13,
29(11)38,
29(11)51,
29(11)274,
29(11)328,
30(3)71,
30(3)119,
30(8)179
- must,
25(6)137,
26(6)145,
27(7)1,
27(7)82,
27(7)273,
27(9)285,
28(3)363,
28(3)367,
28(6)1,
28(6)90,
28(6)156,
28(7)13,
29(6)49,
29(6)278,
29(8)59,
29(11)2,
29(11)145,
29(11)171,
30(11)88
- necessary,
25(6)150,
27(7)94,
27(9)248,
28(3)299,
28(6)46,
28(6)126,
29(6)13,
29(6)206,
29(8)1,
29(11)319,
30(6)186,
30(6)315,
30(8)156,
30(11)134,
33(7)19,
33(7)27
- Nilsen, Kelvin D.,
29(11)76,
29(11)76-1,
30(11)20
- nondeterminism,
29(6)349,
29(6)349-1
- order,
25(6)1,
25(6)16,
27(7)12,
27(7)116,
27(7)152,
28(3)299,
28(3)361,
28(6)156,
28(6)237,
28(6)278,
28(6)300,
28(7)119,
29(6)147,
29(6)349,
29(6)349-1,
29(7)15,
29(8)1,
29(8)35,
29(8)59,
29(11)51,
29(11)86,
29(11)263,
30(3)71,
30(3)94,
30(6)116,
30(6)151,
30(6)174,
30(6)205,
30(6)233,
30(6)246,
30(8)1,
30(8)144,
30(8)189,
30(8)199,
33(7)51
- particular,
25(6)102,
25(6)246,
27(7)82,
27(7)116,
28(6)90,
28(7)23,
29(6)121,
29(8)46,
30(3)71,
30(3)111,
30(6)67,
30(6)291,
30(6)301,
30(8)58,
30(11)79,
30(11)134
- perform,
26(6)219,
27(7)12,
27(7)32,
27(7)82,
27(7)200,
28(6)156,
28(6)177,
28(6)237,
28(6)300,
28(8)90,
29(6)49,
29(6)206,
29(11)25,
29(11)145,
29(11)158,
29(11)171,
29(11)319,
30(3)94,
30(6)151,
30(6)163-1,
30(6)186,
30(6)205,
30(8)48,
30(8)80-1,
30(8)123,
30(8)217,
30(11)7
- PERFORMANCE,
27(9)76,
27(9)111,
27(9)124,
27(9)137,
27(9)162,
27(9)175,
27(9)187,
27(9)248,
27(9)262,
27(9)274,
29(6)186,
29(11)51,
29(11)61,
29(11)98,
29(11)110,
29(11)122,
29(11)183,
29(11)219,
29(11)232,
29(11)242,
29(11)252,
29(11)274,
29(11)308,
29(11)319,
29(11)328,
30(11)31,
30(11)60,
30(11)70,
30(11)79,
31(9)2-1,
31(9)138,
31(9)160,
31(9)258,
31(9)268,
33(11)71,
33(11)92,
33(11)105,
33(11)115,
33(11)170,
33(11)181,
33(11)193,
33(11)205,
33(11)218,
33(11)228,
33(11)240,
33(11)272,
33(11)283,
33(11)295
- performed,
25(6)272,
27(7)1,
27(7)32,
27(7)116,
27(7)188-1,
28(3)299,
28(6)1,
28(6)26,
28(6)68,
28(6)78-1,
28(6)207-1,
28(7)239,
29(6)49,
30(3)13,
30(6)67,
30(8)68
- practical,
26(6)15,
26(11)1,
27(7)32,
27(7)273,
28(3)209,
28(3)271,
28(6)1,
28(6)68,
28(6)227,
29(6)337,
29(6)337-1,
29(9)77,
29(11)208,
30(6)116,
30(8)134,
30(8)156,
30(12)4,
31(5)117,
32(8)136,
32(10)318,
33(3)57,
33(10)388,
33(10)388-1,
33(12)20-1,
34(2)26,
34(4)19-1,
34(6)18-1,
34(6)z-2,
34(10)292,
34(12)18-1
- programmer,
25(6)102,
25(6)283,
27(6)10,
27(7)188-1,
27(8)14,
27(9)262,
27(9)285,
28(3)177,
28(6)1,
28(6)156,
28(6)177,
28(7)13,
28(7)33,
28(7)208,
28(7)239,
29(1)53,
29(8)1,
30(4)13,
30(6)67,
30(8)11,
30(8)29,
30(8)179,
30(8)207,
30(8)217,
30(11)99,
30(11)108,
31(1)6,
31(1)6-1,
31(3)5,
31(3)5-1,
31(3)6,
31(3)6-1,
31(3)8,
31(3)8-1,
33(7)59,
33(7)75,
34(1)338
- rather,
25(6)223,
25(6)234,
25(6)272,
25(6)296,
27(9)223,
27(9)285,
28(3)271,
28(3)361,
29(6)135,
29(6)349,
29(6)349-1,
29(8)119,
29(11)86,
29(11)110,
30(3)111,
30(6)13,
30(6)151,
30(6)174,
30(11)88,
33(7)19
- recent,
25(4)73,
25(6)9,
25(6)85-1,
26(1)14,
27(5)z,
29(11)219,
29(11)232,
30(3)62,
30(6)13,
30(8)134,
30(11)125,
34(2)32-1
- reliable,
27(9)10,
29(11)51
- required,
25(1)59,
25(6)102,
25(6)112,
25(6)272,
25(6)337,
27(9)248,
28(3)299,
29(6)302,
29(11)76-1,
29(11)98,
29(11)171,
29(11)196,
29(11)319,
30(6)139
- research,
26(1)14,
26(3)9,
27(5)z,
27(7)1,
28(6)156,
28(6)187,
28(9)26,
28(11)9,
28(11)9-1,
29(8)94,
29(11)25,
29(11)145,
29(12)31,
29(12)78,
30(3)103,
30(6)270,
30(6)279,
30(8)39,
30(8)134,
30(11)60,
30(11)146-1,
32(1)59,
32(1)92,
32(10)162-1,
34(4)16
- resulted,
29(6)186,
29(11)2
- Rygg, Bernt,
30(11)20
- sequence,
27(3)71,
27(7)224,
27(7)322,
27(7)341,
27(8)83,
27(9)223,
28(6)13,
28(6)26,
28(6)36,
28(7)119,
28(7)149,
28(8)77,
28(8)77-1,
28(12)32,
29(2)33,
29(6)61,
29(9)64,
29(11)274,
29(11)286,
30(8)102,
30(8)134,
30(11)41,
30(11)99,
31(5)249
- since,
25(6)189,
25(6)209,
25(6)272,
27(7)106,
27(7)152,
27(7)273,
28(3)37,
28(6)166,
28(6)237,
28(6)278,
29(6)230,
29(6)337,
29(6)337-1,
29(6)349,
29(6)349-1,
29(11)286,
30(3)23,
30(6)151,
30(6)218,
30(11)7,
30(11)31,
30(11)88,
33(11)252
- task,
25(4)73,
25(6)174,
27(7)68,
27(7)200,
27(7)283,
28(1)32,
28(3)347,
28(6)13,
28(7)13,
28(8)109,
28(8)109-1,
29(10)51,
30(8)123,
30(8)134,
30(8)189,
30(11)7,
30(11)79,
30(11)99,
30(11)125,
30(11)134,
32(7)1,
33(7)19,
33(7)59,
33(7)83
- them,
27(7)152,
27(9)262,
28(3)149,
28(6)90,
28(7)129,
28(7)229,
29(6)49,
29(11)196
- time, real-,
25(3)147,
25(4)20,
25(5)124,
25(10)289,
27(3)66,
28(3)299,
28(3)343,
28(3)353,
28(6)166,
28(6)166-1,
29(7)43,
29(8)22,
29(9)149,
29(10)85,
29(10)301,
29(10)453,
29(11)76,
29(11)76-1,
29(12)11,
30(3)83,
30(11)7,
30(11)31,
30(11)41,
30(11)50,
30(11)60,
30(11)70,
30(11)79,
30(11)88,
30(11)108,
30(11)117,
30(11)124,
30(11)125,
30(11)134,
30(11)146,
30(11)146-1,
33(7)67,
34(3)118,
34(3)130,
34(7)65-1,
34(7)73,
34(12)67
- trend,
27(7)1,
27(9)248,
29(11)308,
30(3)62,
31(1)2-1,
34(5)z-1
- worst-case,
28(6)166,
28(7)129,
29(11)76-1,
30(11)1,
30(11)20